爬楼梯
Climbing Stairs
每次可以爬 1 级或 2 级，问爬到第 n 级共有多少种不同方法。
在力扣中练习题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶
示例 2：
输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶
提示：
1 <= n <= 45
解题思路
动态规划 · 一维状态
最后一步要么跨 1 级，要么跨 2 级
设 dp[i] 为爬到第 i 级的方案数。最后一步只有两种可能：
- 从 i-1 跨 1 级上来；
- 从 i-2 跨 2 级上来。
所以 dp[i] = dp[i-1] + dp[i-2]。边界是 dp[0]=1（站在地面，什么都不做也是一种方案）和 dp[1]=1。
dp[0]=1（不走），dp[1]=1（跨 1 级）；从第 2 级开始递推。
dp[i] = 爬到第 i 级的方案数；最后一步跨 1 级或 2 级
dp[0]=1自拟 n=6，序列是 1,1,2,3,5,8,13，正好是斐波那契。画面上每个目标格只依赖左边两个格子，写完就不会再改。
第 5 级：可以从 4 跨 1 级，或从 3 跨 2 级，共 8 种。
- i
- 5
- dp[i]
- 8
dp[i] = 爬到第 i 级的方案数；最后一步跨 1 级或 2 级
dp[5]=dp[4] + dp[3]5 + 3=8时间 O(n)，空间 O(n)；如果只保留前两个状态，空间可以降到 O(1)。
易错点
- dp[0] 设为 0：dp[2] 会少一种“直接跨 2 级”的方案。
- 把 dp[i] 定义成“跨到 i 的步数”而不是方案数：加法含义完全不同。
- n=1 没有单独处理：dp[1] 越界或初始化错误。
滚动变量 · O(1) 空间
只留前两个数，像求斐波那契一样滚动
时间相同，但只保存前两个状态，空间 O(1)；代价是丢失完整 dp 表，不便回溯方案。
递推只用到 dp[i-1] 和 dp[i-2]，更早的状态永远不会再被读取。于是用两个变量 prev1、prev2 滚动更新即可。
每轮计算 cur = prev1 + prev2，然后 prev2 = prev1、prev1 = cur。空间从 O(n) 降到 O(1)。
如果题目还要求输出具体方案（而不只是数量），就必须保留路径信息，不能只用滚动变量。
- 1n<=2 直接返回 n。
- 2prev2=1，prev1=2。
- 3循环 cur=prev1+prev2，两个变量后移。
- 4返回 prev1。
易错点
- 更新顺序写反：先用 cur 覆盖 prev1，再更新 prev2，会丢掉旧值。
- n=1 时直接进入循环：prev1/prev2 的初始含义与 n 不匹配。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
n = 6dp[0]=1（不走），dp[1]=1（跨 1 级）；从第 2 级开始递推。
dp[i] = 爬到第 i 级的方案数；最后一步跨 1 级或 2 级
dp[0]=1查看 C++ 代码
延伸阅读
- 爬楼梯是斐波那契的变体；状态定义和边界比转移方程更容易写错。
- 同类题：打家劫舍、使用最小花费爬楼梯，都是“最后一步”视角的一维 DP。