盘锦市网站建设_网站建设公司_建站流程_seo优化

【LeetCode 70】爬楼梯（C++）解题思路与代码实现

在LeetCode的算法题中，爬楼梯是一道经典的入门动态规划题目，其核心思想是通过递推关系找到问题的解。本文将详细讲解这道题的解题思路，并给出C++的实现代码，同时分析不同解法的优劣。

一、题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

提示： 1 <= n <= 45

示例：

- 输入： n = 2 ，输出： 2 （1阶+1阶、2阶）
- 输入： n = 3 ，输出： 3 （1+1+1、1+2、2+1）

二、解题思路

这道题的核心是找到递推公式，我们可以通过分析小规模的情况推导规律：

1. 当 n = 1 时，只有1种方法（爬1阶）；
2. 当 n = 2 时，有2种方法（1+1、2）；
3. 当 n = 3 时，到达第3阶的最后一步只能是从第2阶爬1阶，或从第1阶爬2阶，因此方法数为 f(2) + f(1) = 3 ；
4. 以此类推，对于第 n 阶，方法数 f(n) = f(n-1) + f(n-2) 。

这本质上是斐波那契数列的应用，只是初始条件略有不同（斐波那契数列通常以 f(0)=0, f(1)=1 开头，本题 f(1)=1, f(2)=2 ）。

解法选择

- 递归：直接按递推公式递归，但会存在大量重复计算，时间复杂度为 O(2^n) ，当 n=45 时会超时；
- 动态规划（迭代）：用变量保存中间结果，避免重复计算，时间复杂度 O(n) ，空间复杂度 O(1) ，是本题的最优解。

三、C++代码实现

这里采用迭代法实现，仅用三个变量保存中间值，空间复杂度优化至 O(1) ：

cpp
class Solution {
public:
int climbStairs(int n) {
// 处理边界情况：n=1返回1，n=2返回2
if (n <= 2) {
return n;
}
// a表示f(n-2)，b表示f(n-1)，c表示f(n)
int a = 1, b = 2, c = 0;
// 从第3阶开始迭代计算到第n阶
for (int i = 3; i <= n; ++i) {
c = a + b; // 计算当前阶的方法数
a = b; // 递推：a变为下一次的f(n-2)
b = c; // 递推：b变为下一次的f(n-1)
}
return c;
}
};


代码解释

1. 边界处理：当 n≤2 时，直接返回 n ，因为这两种情况的方法数是确定的；
2. 变量初始化： a 初始为 f(1)=1 ， b 初始为 f(2)=2 ， c 用于存储当前阶的方法数；
3. 迭代计算：从第3阶开始，依次计算每一阶的方法数，通过递推更新 a 和 b ，最终 c 即为 f(n) 。

四、测试用例验证

我们可以通过几个测试用例验证代码的正确性：

1. 输入 n=1 ，输出 1 ，符合预期；
2. 输入 n=2 ，输出 2 ，符合预期；
3. 输入 n=3 ，输出 3 ，符合预期；
4. 输入 n=5 ，输出 8 （方法：1+1+1+1+1、1+1+1+2、1+1+2+1、1+2+1+1、2+1+1+1、1+2+2、2+1+2、2+2+1）。

五、总结

爬楼梯问题是动态规划的入门经典题，其核心是找到递推关系并通过迭代优化时间和空间复杂度。本题的迭代解法将时间复杂度控制在 O(n) ，空间复杂度优化至 O(1) ，能够高效处理题目给定的 n≤45 的范围。

对于这类递推型问题，我们需要先通过小规模案例推导规律，再选择合适的解法（递归/迭代/动态规划），同时注意优化重复计算和空间占用