70. 爬楼梯（Climbing Stairs）
频次 ★★★★★ · 难度 🟢 · 高频：全厂
题目
每次可以爬 1 或 2 阶，到楼顶 n 阶有多少种不同方法。
示例：
输入: n = 3
输出: 3 （1+1+1, 1+2, 2+1）
思路
DP 入门：到达第 i 阶 = 从 i-1 迈 1 步 + 从 i-2 迈 2 步。dp[i] = dp[i-1] + dp[i-2]，实际上就是斐波那契数列。
空间可优化：只用两个变量滚动。
代码
public int climbStairs(int n) {
if (n <= 2) return n;
int a = 1, b = 2; // dp[1], dp[2]
for (int i = 3; i <= n; i++) {
int c = a + b;
a = b;
b = c;
}
return b;
}复杂度
- 时间：O(n)
- 空间：O(1)
边界条件
- n = 1：1 种
- n = 2：2 种（1+1, 2）
变式
- 746. 使用最小花费爬楼梯：每阶有消耗，取 min
- 三步问题：
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
易错点
- 第 n 阶是下标 n 不是 n-1——通常 dp[0] 表示地面（0 阶），dp[1]=1、dp[2]=2
- 斐波那契数列不要写成递归（指数爆炸），用迭代或矩阵快速幂
面试追问
- 如果一次能爬 1~k 阶？ 广义斐波那契：
dp[i] = sum(dp[i-1] + ... + dp[i-k])，注意 dp[0]=1