爬楼梯
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
1 <= n <= 45
示例 1
示例 2
模拟答题者思考
1. 最直接：对每一步枚举「下一步走 1 阶还是 2 阶」，用 DFS 回溯数所有路径，指数级分支，n=45 必超时。
2. 重复在哪里？到达第 i 阶的路径数，只取决于「到达 i-1 再迈 1 步」和「到达 i-2 再迈 2 步」——子问题 f(i) 与具体路径无关，只与阶数有关，大量子树重复计算。
3. 关键转化：定义 f(i) = 到第 i 阶的方法数，则 f(i) = f(i-1) + f(i-2)，边界 f(1)=1, f(2)=2（或 f(0)=1, f(1)=1 再推）。这就是斐波那契数列，与 #509 同源。
4. 手推 n=3：f(1)=1, f(2)=2, f(3)=f(2)+f(1)=3，对应 1+1+1、1+2、2+1，与样例一致。
5. 数组版 O(n) 空间可压成两个变量 prev, cur 滚动，每阶 O(1) 更新，总时间 O(n)、空间 O(1)。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
dp[i]（或 prev, cur） | int | 定义：到达第 i 阶台阶的方法总数（i 从 0 到 n，其中 dp[0]=1 表示站在地面）维护：最后一跳要么从 i-1 跨 1 阶上来，要么从 i-2 跨 2 阶上来，两种来源的方法数相加更新： dp[i] = dp[i-1] + dp[i-2]；滚动数组时 cur = prev + cur 再整体前移 |
prev | int | 定义：上一阶（相当于 dp[i-2]）的方法数维护：每推进一步，原来的 cur 变成新的 prev更新：初始 prev=1（对应 dp[0] 或 dp[1] 的上一状态，依实现从 n=1 或 n=2 起循环） |
cur | int | 定义：当前阶（相当于 dp[i-1] 或正在计算的 dp[i]）的方法数维护：每轮用 prev + cur 得到下一阶，再滚动赋值更新：初始 cur=1（n=1 只有一种爬法）；循环 n-2 或 n-1 次后 cur 即为答案 |
i | int | 定义：从低阶向第 n 阶推进的循环计数维护： for _ in range(2, n+1) 或等价次数，每轮只依赖前两阶状态更新：每轮计算新 cur 并滚动 prev |
落码步骤
1. 特判 n <= 2：直接返回 n（1→1 种，2→2 种）
2. 初始化 prev = 1、cur = 2（分别表示到第 1、2 阶的方法数）
3. 循环 i 从 3 到 n：令 nxt = prev + cur
4. 滚动：prev = cur，cur = nxt
5. 循环结束返回 cur（即到第 n 阶的方法数）
代码实现
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 2:
return n
prev, cur = 1, 2
for _ in range(3, n + 1):
nxt = prev + cur
prev, cur = cur, nxt
return curclass Solution {
public:
int climbStairs(int n) {
if (n <= 2) return n;
int prev = 1, cur = 2;
for (int i = 3; i <= n; ++i) {
int nxt = prev + cur;
prev = cur;
cur = nxt;
}
return cur;
}
};
// 时间 O(n)，空间 O(1)复杂度分析
O(n)
O(1)
常见坑
边界下标：若用 dp[0]=1, dp[1]=1 推斐波那契，注意循环起点与最终返回的是 dp[n] 还是 dp[n-1]，不要与「n=2 返回 2」的题意搞混。
递归不加记忆化会重复计算同一阶，n=45 会栈/时间爆炸；要么 memo，要么改迭代滚动。
滚动更新顺序：须先算 nxt = prev + cur 再赋值，不能在同一行错误覆盖导致少加一项。
必测边界 Case
1 → 1（只能一步一阶）
2 → 2（1+1 或 2）
3 → 3（官方示例 2）
n = 45（题目上限，验证 O(n) 迭代在 int 范围内：结果 1836311903）