题目
你正在爬楼梯。需要
n 阶你才能到达楼顶，每次可以爬 1 或 2 个台阶，问有多少种不同的方法可以爬到楼顶。
输入: n = 3
输出: 3
解释: 1+1+1、1+2、2+1，共三种。
这是几乎所有动态规划教材的第一题 —— 递推式人人都会写。但美团的社招面试把它续了一句：「
n = 80 呢？」这一问不是考递推的，是考你知不知道自己的
int 在第 46 阶就已经装不下了。本文把三层都走一遍：递推怎么来的、
O(2^n) 从哪来、以及 n=80 时先爆掉的是类型而不是算法。
一、核心洞察：最后一步只有两种来路
爬到第
i 阶的最后一步，只有两种可能：
- 从第
i-1 阶迈 1 阶上来；
- 从第
i-2 阶迈 2 阶上来。
这个分类有两个关键性质：
互斥（最后一步不可能同时既是 1 阶又是 2 阶）和
完备（除了这两种没有第三种迈法）。互斥且完备的分类才能直接相加 —— 这就是加法原理，也是所有计数型 DP 的第一课：
dp[i] = dp[i-1] + dp[i-2]，其中 dp[i] 是爬到第 i 阶的走法数。
注意这个「最后一步分类法」和
LC 300 的「以 i 结尾」锚是同一招：
把一个纠缠不清的全局问题，压缩成只看边界的一步决策。这里更极端 —— 只看最后一步，而它恰好只有两种来路。
初值不是凑出来的：
dp[0] = 1（站在地面不动，也算一种走法 —— 空方案），
dp[1] = 1（只能迈一步）。把
dp[0] 填成 0 的代码会在
dp[2] 上就错成 1（见 9.3）。
这个递推能成立，还依赖一个隐含前提：
无后效性 —— 第
i 阶之后的走法，不会改变「到第
i 阶有几种走法」这个数。所以可以从左往右一路填，填过的格子永远不用改。这题的决策只有 1 和 2 两种、且互不影响，无后效性天然成立；等遇到「不能连续迈两个 2 阶」这类约束，它就会被打破，状态要多记一维（见十、变体）。
二、拆解：加法原理 = 互斥且完备
def climbStairs(n: int) -> int:
if n <= 1:
return 1
dp = [0] * (n + 1)
dp[0], dp[1] = 1, 1 # 空方案也是一种走法
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
写完顺手看一眼数列：
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 … —— 就是
斐波那契（LC 509）。事实上
ways(n) = Fib(n+1)（
Fib(1) = Fib(2) = 1），两道题是同一个递推换了个故事。这不是巧合：
「最后一步只有两种来路」和「斐波那契的递推」是同一句话。
空间立刻可以压到两个变量 —— 而且这题没有任何坑（不涉及 LC 72 那种「对角线被覆盖」），因为依赖方向只有两个紧邻的前驱：
def climbStairs(n: int) -> int:
a, b = 1, 1 # dp[0], dp[1]
for _ in range(2, n + 1):
a, b = b, a + b
return b if n >= 1 else a
三、动画怎么看
第一个动画是
n = 10 的填表过程：11 个格子从左往右点亮，每一格先用两条弧线把「来路」拉出来 —— 绿弧从
i-1（迈 1 阶）、橙弧从
i-2（迈 2 阶）—— 然后两数相加落进格子。
- 横幅：左边在算第几阶，中间本帧的来路，右边贡献值；
- 格子：还没算到的画虚线空壳，正在算的画橙框，落笔的瞬间转金；
- 两条弧线：
from1 帧只亮绿弧、from2 帧再加橙弧，settle 帧两条都在、格子定金 —— 三帧正好对应「分类、补全、相加」；
- 收尾：整行
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89，答案 dp[10] = 89。
值得盯的一帧是
i = 2：绿弧带来
dp[1] = 1、橙弧带来
dp[0] = 1 ——
dp[0] 在这里被正经消费了一次，这就是它必须是 1 而不是 0 的原因。
四、完整推演表
以
n = 10 为主例（对应动画的 29 帧）：
dp[10] = dp[9] + dp[8] = 55 + 34 = 89。验证一下语义：10 阶楼梯用
k 个 2 阶、
10-2k 个 1 阶，排列数
C(10-k, k)，求和
C(10,0)+C(9,1)+C(8,2)+C(7,3)+C(6,4)+C(5,5) = 1+9+28+35+15+1 = 89 —— 组合数公式和递推在每一项上都对得上（脚本核到 n=40）。
五、进阶：递归树与 n=80 的溢出
5.1 递归树：O(2^n) 从哪来
递推反过来写就是朴素递归
f(k) = f(k-1) + f(k-2)。把它展开成一棵树，
O(2^n) 就不是一句口号了 —— 下图是
n = 6 的完整调用树，按真实执行顺序（前序 DFS）逐个点亮：
n = 6 时这棵树有
25 个节点、13 个叶子，但不同的
k 只有 7 个：
f(2) 被从头算了
5 次、
f(0) 5 次、
f(1) 8 次 —— 红色的节点全是重复子问题，每个下面还挂着一整棵相同的子树。叶子恰好 13 个不是巧合：
每条根到叶子的路径，就是把 n 拆成若干个 1 和 2 的一种走法，所以叶子数 =
ways(n)。
调用次数
T(n) = 2·Fib(n+1) - 1：
n = 40 就要
3.3 亿次调用，
n = 50 是 407 亿次。加一个
memo 数组，25 次调用变 7 次 —— 这就是从
O(2^n) 到
O(n) 的全部内容。
5.2 美团追问：n=80 —— 先爆的是类型
然后是那句话：「
n = 80 呢？」算法还是那个算法，但答案已经装不进默认类型了。下面把每一阶的走法数排成一条色带，绿色装得进
int32、红色装不下：
分界点都是可以精确算出来的（以下数字全部经脚本核实）：
所以
n = 80 的答案是
ways(80) = 37889062373143906 ——
int 早就爆了（46 阶就爆），long 装得下但只够撑到 91 阶。面试官要听的就是这三层：
int 不行、
long 勉强、再大上
BigInteger（或题目改成对
1e9 + 7 取模）。
为什么类型追不上：走法数每阶约乘 1.618（黄金比 ——
ways(80)/ways(79) = 1.6180339887...），是
乘性增长；而类型的位宽是固定的，
log2 之后是一段固定的可表示范围。乘性增长撞线性宽度，46 阶就撞上了。
六、Java 版
三档写法，按 n 的范围选：
// n <= 45：int 够用（ways(45) = 1836311903 是 int32 最后一个）
public int climbStairs(int n) {
int a = 1, b = 1; // dp[0], dp[1]
for (int i = 2; i <= n; i++) {
int next = a + b; // 先算 next，再挪 —— 顺序反了就丢 dp[i-1]
a = b;
b = next;
}
return n >= 1 ? b : a;
}
// n <= 91：换 long（ways(91) = 7540113804746346429 是 int64 最后一个）
public long climbStairsLong(int n) {
long a = 1, b = 1;
for (int i = 2; i <= n; i++) {
long next = a + b;
a = b;
b = next;
}
return n >= 1 ? b : a;
}
// 题目若要求对 1e9+7 取模（或 n 特别大直接上 BigInteger）
import java.math.BigInteger;
public BigInteger climbStairsBig(int n) {
BigInteger a = BigInteger.ONE, b = BigInteger.ONE;
for (int i = 2; i <= n; i++) {
BigInteger next = a.add(b);
a = b;
b = next;
}
return n >= 1 ? b : BigInteger.ONE;
}
取模版就是中间那档把
long next = (a + b) % 1_000_000_007L ——
每步都取模，不是最后才取：
long 里累加 90 多项不改，中途就溢出了。
七、边界情况
- n = 0：约定答案为 1（空方案）。LC 70 的约束是
1 <= n <= 45，但 dp[0] = 1 这个约定在递推里被正经用到（dp[2] = dp[1] + dp[0]），不是摆设。
- n = 1 / n = 2：1 / 2 —— 面试时先报这两个最小值，确认双方对「走法」的定义一致（
1+1 和 2 算两种）。
- 两个变量版的返回：
n = 0 时循环一次都不跑，返回的是 a 而不是 b —— 上面代码里的 n >= 1 ? b : a 就是给这个留的。
- JS 的精度：
Number 是 double，ways(78) = 14472334024676221 起就不是精确整数了。JS 想算 n=80 得上 BigInt（1n + 2n），或者接受精度丢失。
八、复杂度
一个诚实的脚注：上了
BigInteger 之后「O(n)」要打折扣 —— n=80 时每个数约 27 位十进制（96 个二进制位），加法不再是 O(1)，总时间约
O(n · n/字长)。面试里能主动提这一句，比背复杂度表值钱。
九、常见坑
9.1 int 溢出（官方样例恰好看不出来）
官方样例
n = 2、
n = 3，答案是个位数 —— 用
int 写，LeetCode 上
全绿。但
ways(46) = 2971215073 > 2147483647，第 46 阶就爆了。这是「官方样例掩盖 bug」系列里最现实的一期：
bug 不在算法里，在类型里，而评测用例的 n 最大才 45。美团的 n=80 追问就是奔着这个来的。
9.2 朴素递归不带记忆化
n = 40 要 3.3 亿次函数调用（精确值
2·Fib(41) - 1 = 331160281），本地跑直接卡死。面试写递归版没问题，但要说清「这是 O(2^n)，加个 memo 就是 O(n)」—— 说不出这句话，前面写的都对不了。
9.3 dp[0] 填成 0
dp[2] = dp[1] + dp[0]。
dp[0] = 0 时
dp[2] = 1（应为 2），整个表从第三格开始全错。根因是没想清楚「不动也算一种走法」—— 空方案是计数的合法成员。官方样例
n=2 恰好会输出 1 而不是 2，所以这个坑样例能抓住；但
dp[0]=0 配
dp[1]=2 的奇怪初值组合，样例就看不出来了。
9.4 两个变量的更新顺序
a, b = b, a + b（Python 的元组赋值天然安全）；Java 必须先存
next = a + b 再挪
a = b; b = next。直接写
a = b; b = a + b 会把
新 a 加进
b —— 递推变成别的数列。这和 LC 72 的
prev 备份是同一类问题：
覆盖之前的那一刻，是拿到旧值的唯一机会。
9.5 取模变体忘了每步取模
题目改成「答案对
1e9 + 7 取模」时，要在
每一步加法后取模。Java 里不取模的
long 在 92 阶后溢出成负数；最后才
% MOD 补救不了已经溢出的中间值。Python 的整数无限精度，取模只是为了数值变小、乘法不膨胀。
9.6 把「斐波那契」当口诀跳过推导
直接背
dp[i] = dp[i-1] + dp[i-2] 的风险在追问：为什么是加法？（互斥且完备）为什么没有系数 2？（分类是按最后一步，不是按台阶）n=80 为什么爆？（类型宽度 vs 乘性增长）—— 三问挂一，这题就白做了。
十、面试怎么答
- 先立「最后一步分类」："到第 i 阶的最后一步只有从 i-1 迈 1、从 i-2 迈 2 两种来路，互斥且完备，所以 dp[i] = dp[i-1] + dp[i-2]，dp[0]=1 是空方案。"
- 顺手点破斐波那契："ways(n) = Fib(n+1)，这题和 LC 509 是同一个递推。"
- 主动讲 O(2^n) 的来源："朴素递归展开是一棵树，n=6 就有 25 个节点、f(2) 算 5 次 —— 叶子数恰等于 ways(n)。加 memo 变 O(n)。"
- 空间 O(1)："依赖只有两个紧邻前驱，两个变量滚动就够，没有 LC 72 那种对角线问题。"
- 接住 n=80："
int 在 46 阶爆（ways(46)=2971215073），long 撑到 91 阶，n=80 的答案是 37889062373143906 —— 要么 long、要么 BigInteger、要么题目改成对 1e9+7 取模且每步取模。"
- 报变体：LC 746 最小花费爬楼梯（计数变最值，加号变 min）；一次能迈 1..m 阶（dp[i] = 前缀和，窗口滑动）；不能连续迈两个 2 阶之类的约束（状态要多一维「上一步是什么」）；矩阵快速幂
O(log n)。
结语
爬楼梯是「计数型 DP」的第一课，但它的三层考点是递进的：
第一层是加法原理 —— 互斥且完备的分类才配相加；第二层是递归树 —— O(2^n) 不是口令，是 25 个节点里 18 个重复的现场；第三层是类型 —— 增长是乘性的，类型的位宽是线性的，46 阶就撞车。 上一给状态加锚（LC 300）、上一给转移补一格缓存（LC 72），这一篇往下打地基：所有 DP 的第一行递推，都值得问一句「这个分类为什么不重不漏」—— 以及面试官微微笑着说 n=80 的时候，你脑子里有没有那根类型宽度的弦。