C++ 算法 LeetCode 编号 70 - 爬楼梯-开发者社区

【计时开始 - 15分钟】

7-12 分钟：编写 C++ 代码

12-14 分钟：简单测试与代码审查

【比赛结束】

C++ 版快闪赛的特点

如果您喜欢此文章，请收藏、点赞、评论，谢谢，祝您快乐每一天。

【计时开始 - 15分钟】

0-2 分钟：理解题目，识别模式

同前，这是斐波那契数列变种。
F(n) = F(n-1) + F(n-2)，F(1)=1,F(2)=2。

2-7 分钟：设计 C++ 实现思路

算法选择：动态规划，迭代法，O(1) 空间。
C++ 工程落地考虑：
- 类和方法：通常在Solution类中实现public int climbStairs(int n)方法。
- 整数范围：n <= 45。int类型在 C++ 中通常是 32 位，最大值约 2.1 x 10^9。F(45)约 1.8 x 10^9，在int范围内，足够。
- 变量：需要两个变量存储前两项的值。
- 循环：从 3 迭代到 n。
- 边界处理：n=1,n=2。

7-12 分钟：编写 C++ 代码

#include <vector> // 如果需要 vector, 尽管这里 O(1) 空间不需要

// LeetCode 平台通常要求在 Solution 类中实现
class Solution {
public:
/**
* @brief 计算爬 n 阶楼梯的总方法数。
*
* @param n 楼梯总阶数 (1 <= n <= 45)。
* @return 到达楼顶的不同方法数。
*
* @details
* 思路：这是一个经典的斐波那契数列问题。
* 到达第 i 阶的方法数，等于到达第 i-1 阶（再走1步）与到达第 i-2 阶（再走2步）的方法数之和。
* 令 F(i) 为到达第 i 阶的方法数。
* 递推关系：F(i) = F(i-1) + F(i-2)。
*
* 边界条件：
* F(1) = 1 (只可能走 1 步)
* F(2) = 2 (可能走 1+1 或 2)
*
* 采用动态规划（迭代法）实现，空间复杂度为 O(1)，时间复杂度为 O(n)。
* C++ 的 int 类型足够存储 F(45) 的结果。
*/
int climbStairs(int n) {
// 处理基本边界情况
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}

// 使用 O(1) 空间复杂度的动态规划
// prev2 存储 F(i-2) 的值，prev1 存储 F(i-1) 的值
int prev2 = 1; // 对应 F(1)
int prev1 = 2; // 对应 F(2)

// 从第 3 阶开始迭代计算，直到第 n 阶
// 循环会执行 n - 2 次
for (int i = 3; i <= n; ++i) {
// 计算当前阶数的方法数
int currentWays = prev1 + prev2;

// 更新 prev2 和 prev1，为下一轮迭代做准备
prev2 = prev1; // 原来的 F(i-1) 变为下一轮的 F(i-2)
prev1 = currentWays; // 新计算出的 F(i) 变为下一轮的 F(i-1)
}

// 循环结束后，prev1 中存储的就是 F(n) 的值
return prev1;
}
};

12-14 分钟：简单测试与代码审查

示例 1：n = 2
- 直接返回 2。正确。
示例 2：n = 3
- prev2 = 1,prev1 = 2
- i = 3:currentWays = 2 + 1 = 3.prev2 = 2,prev1 = 3.
- 循环结束，返回prev1(3)。正确。
考虑 n=1：代码已处理。
代码风格：
- class Solution { public: ... };符合 LeetCode C++ 模板。
- 方法签名int climbStairs(int n)标准。
- 变量命名prev1,prev2,currentWays良好。
- 注释：使用 C++ 的/** ... */风格进行多行文档注释，解释了思路、递推关系、边界条件和复杂度。@brief,@param,@return,@details标签是 Doxygen 风格，可用于生成文档，是 C++ 中常见的良好实践。
- for (int i = 3; i <= n; ++i)：C++ 风格的 for 循环，++i相对于i++在某些场景下有微小性能优势（虽然在此处不构成显著影响，但体现了 C++ 开发者的一些习惯）。
工程落地：代码结构清晰，逻辑正确，注释详尽且符合 C++ 规范。

14-15 分钟：最终检查

代码逻辑正确，通过示例。
符合 C++ 和 LeetCode 提交要求。
整数int足够。
包括了必要的头文件#include <vector>(即使未使用，有时也习惯性包含，或可以去掉以更精炼)。

【比赛结束】

最终提交（模拟）：

#include <vector> // 通常 LeetCode 示例会包含，或可根据需要添加

// LeetCode 平台通常要求在 Solution 类中实现
class Solution {
public:
/**
* @brief 计算爬 n 阶楼梯的总方法数。
*
* @param n 楼梯总阶数 (1 <= n <= 45)。
* @return 到达楼顶的不同方法数。
*
* @details
* 思路：这是一个经典的斐波那契数列问题。
* 到达第 i 阶的方法数，等于到达第 i-1 阶（再走1步）与到达第 i-2 阶（再走2步）的方法数之和。
* 令 F(i) 为到达第 i 阶的方法数。
* 递推关系：F(i) = F(i-1) + F(i-2)。
*
* 边界条件：
* F(1) = 1 (只可能走 1 步)
* F(2) = 2 (可能走 1+1 或 2)
*
* 采用动态规划（迭代法）实现，空间复杂度为 O(1)，时间复杂度为 O(n)。
* C++ 的 int 类型足够存储 F(45) 的结果，因为 F(45) 约 1.8 x 10^9 < INT_MAX (约 2.1 x 10^9)。
*/
int climbStairs(int n) {
// 处理基本边界情况
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}