70. 爬楼梯（Climbing Stairs）¶
频次 ★★★★★ · 难度 🟢 · 高频：全厂
题目¶
每次可以爬 1 或 2 阶，到楼顶 n 阶有多少种不同方法。
示例：
思路¶
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;
}
dp 下标坐标系：独立 Choosing 与全书公约（70 = 雷区第一教训）¶
两个主流流派都对但坐标轴不同（70 实测双版互验全绿）：
| 流派 A（dp[i]=到第 i+1 阶） | 流派 B（dp[i]=到第 i 阶，下标=阶数） | |
|---|---|---|
| 数组长度 | n | n+1 |
| 地基 | dp[0]=1, dp[1]=2 | dp[0]=1(空走), dp[1]=1, dp[2]=2 |
| 循环 | 2..n-1 | 3..n |
| 返回 | dp[n-1] | dp[n] |
全书建议锁流派 B（让 dp 下标与题面量同名）：多花一个 dp[0] 格子+一条"空走法=1 种"地基，换来 n/n-1/n+1 换算的零思维税——62/63/198/300/121 全书统一。
坐标系自查三问（写 DP 前自问）： 1. dp[i] 语义中 i 最大到几 → 数组长度 = 那个数 + 1 2. 最后一个要填的下标 → 循环上限 3. 答案住哪个格子 → return 下标 = ①的语义终点（不是 n 也不是 n-1，除非恰好）
另：dp[0] 的值为 1 还是 0 没有对错、只有流派内自洽——语义"从 0 出发站 0 阶"=1 种空走法 vs "走 0 步不够格"=0。先定语义再定地基，别改测（用例会抓）。
复杂度¶
- 时间：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