机考刷题到第 70 题爬楼梯，很多人会觉得这题太简单了，一个 easy，递归几行就写完。但真到了机考或者面试手写代码的环节，这道题往往能筛掉一批人。LeetCode 70 爬楼梯是 LeetCode 热门 100 题里的钉子户，也是动态规划入门第一课，几乎所有题解都会拿它来阐述“状态转移”这个概念。题目本身一句话能说完，但递归、记忆化、滚动数组、数学公式这些不同解法的选择，直接暴露了你对算法的理解深度。这篇文章我就从机考实战的角度，把这道题从头到尾彻底拆一遍，包括设计思路、推导过程、代码落地、边界处理和避坑清单，希望能给准备机考和刷题的同学一份可以直接照抄的参考。
你走进机考环境，屏幕上只有题目描述和编辑器，紧张感会被无限放大。LeetCode 70 的题干翻译成中文通常是这样：假设你正在爬楼梯，需要 n 阶你才能到达楼顶，每次你可以爬 1 个或 2 个台阶，你有多少种不同的方法可以爬到楼顶。约束条件里 n 是正整数，在 LeetCode 原始题目里 n 的范围通常不超过 45。这个范围意味着结果不会大到超出 int，但也足够让你体会暴力递归是怎么超时的。我第一次刷这道题的时候也没当回事，随手写了个递归提交，结果 Run 出来 TLE，那一刻才意识到，简单题不等于无脑题，机考刷题的意义就在于此。
1. 这题到底在考什么：题目拆解与机考定位
1.1 题目原意与直观感受
先看清楚题目本身。输入一个正整数 n，输出爬到第 n 阶的不同方法数。每次能爬 1 阶或 2 阶，这是一个明确的约束。举个例子，n=3 时有三种方法：1+1+1，1+2，2+1。为什么不是 1+1+1 和 2+1 和 1+2 后两种算不同？因为题目说“不同的方法”，顺序不同也算不同，所以 1+2 和 2+1 是两种独立方案。
如果你手算前几项，会得到一个非常眼熟的数列：
| n | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 方法数 | 1 | 2 | 3 | 5 | 8 | 13 |
这不就是去掉第一项的斐波那契数列吗？很多人看到这里就开始背公式，但机考不只看你最终答案对没对，更看你写代码的过程是否可靠。如果你只是记了一个斐波那契公式，遇到变体题，比如从“每次爬 1 或 2 阶”改成“每次爬 1 或 3 阶”，公式立刻失效，但递推的思路却依然成立。所以真正要训练的，是把“爬楼梯”抽象成状态转移的能力。
1.2 为什么它是机考刷题的“分水岭”
LeetCode 热门 100 题里，70 题通常排在很靠前的位置，原因不是它难，而是它适合当教学案例。机考刷题的人里，一部分人刷到这道题就跳过，觉得太简单；另一部分人认真做了递归、记忆化、动态规划三种写法，并且能把推导过程讲清楚。拉开差距的正是后者。
这道题在机考中的定位非常特殊。它是一道典型的“一维动态规划”题目，后续你遇到打家劫舍、零钱兑换、最长递增子序列，甚至背包问题的雏形，都会回到这个核心逻辑：定义状态、写状态转移方程、确定初始条件、选择计算顺序。如果你在爬楼梯这道题上把逻辑吃透了，后面很多题都会顺很多；如果只是背了代码，机考时题目稍微换个场景，比如改成“爱吃香蕉的狒狒”那种包装过的题，你可能就懵了。
另外，LeetCode 周赛里经常出现类似的签到题，本质就是 70 题的变体。机考不像平时刷题可以反复尝试，往往时间紧张、心态不稳，这种简单题能不能一次 AC，直接影响你在后面中难题上的信心。
2. 由浅入深的四种解法：递推式的理解和代码落地
2.1 暴力递归：帮你看见状态转移
刚开始学这道题，我强烈建议先写一遍暴力递归，不要直接看题解。递归的写法来自一个非常自然的想法：到达第 n 阶，最后一步要么从第 n-1 阶跨 1 阶上来，要么从第 n-2 阶跨 2 阶上来。所以到达第 n 阶的方法数，等于到达第 n-1 阶的方法数加上到达第 n-2 阶的方法数。写成公式就是：
f(n) = f(n-1) + f(n-2)
这个公式就是状态转移方程。很多题解会直接告诉你，但如果你自己推导一遍，印象会深很多。对应的递归代码非常简单：
def climbStairs(self, n: int) -> int: if n == 1: return 1 if n == 2: return 2 return self.climbStairs(n - 1) + self.climbStairs(n - 2)这段代码在 LeetCode 上提交是超时的，原因是时间复杂度为 O(2^n)。每次调用都会分裂成两个子问题，形成一个巨大的递归树。n=45 时，计算量是一个天文数字。递归栈的深度也会达到 n，如果 n 再大一点，就会栈溢出。所以递归版本只能用来理解思路，绝对不能用在实际机考里，不然你会亲眼看着它转圈圈然后超时。
2.2 记忆化搜索：第一次砍掉重复计算
暴力递归为什么慢？因为在计算 f(n) 的时候，f(3) 这种子问题被重复计算了成千上万次。既然一个值已经算过了，为什么不存下来？这就是记忆化搜索，也叫带备忘录的递归。
def climbStairs(self, n: int) -> int: memo = {1: 1, 2: 2} def dfs(k): if k in memo: return memo[k] memo[k] = dfs(k - 1) + dfs(k - 2) return memo[k] return dfs(n)这个版本在原来的递归树上去掉了重复分支，每个 k 只会被计算一次，时间复杂度降到 O(n)，空间复杂度 O(n)。机考时如果实在想用递归，这个版本也能过，但我不推荐作为主方案。原因有两个：一是递归函数调用有额外开销，Python 在大规模输入下可能会很慢；二是当 n 极大时，递归深度可能超出解释器限制，导致 RecursionError。LeetCode 70 的 n 不超过 45，递归深度没问题，但为了养成好的机考习惯，还是优先用迭代。
2.3 自底向上的动态规划：机考的标准答案
记忆化搜索是“自顶向下”，动态规划则是“自底向上”。既然递推公式已经明确了，直接从小的 n 算起，把结果存到数组里。
def climbStairs(self, n: int) -> int: if n <= 2: return n dp = [0] * (n + 1) dp[1] = 1 dp[2] = 2 for i in range(3, n + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[n]这段代码的时间复杂度是 O(n)，空间复杂度也是 O(n)。别急着觉得空间不够好，其实这里还可以继续优化。观察递推式，你会发现计算 dp[i] 时只需要前两个值，dp[i-1] 和 dp[i-2]，再往前的数据根本用不上。所以不需要一整个数组，只需要两个变量不断滚动更新。
def climbStairs(self, n: int) -> int: if n <= 2: return n prev2, prev1 = 1, 2 for _ in range(3, n + 1): prev2, prev1 = prev1, prev2 + prev1 return prev1这就是滚动数组优化。prev2 代表前两个位置的结果，prev1 代表前一个位置的结果，每一轮循环都往前推进一格。生活化类比：就像传送带上的两个箱子，每走一步，后面的箱子顶上前面箱子的位置。最终 prev1 就是 f(n)。这个版本时间复杂度 O(n)、空间复杂度 O(1)，是机考里最推荐的解法。
2.4 斐波那契通项公式：数学解法的边界
因为 f(n) 本质上就是斐波那契数列的第 n+1 项，所以也可以用斐波那契通项公式直接求。公式长这样：
F(n) = ((1 + √5)/2)^n - ((1 - √5)/2)^n) / √5
对应到爬楼梯，答案就是 F(n+1)。Python 可以这样写：
import math def climbStairs(self, n: int) -> int: sqrt5 = math.sqrt(5) phi = (1 + sqrt5) / 2 psi = (1 - sqrt5) / 2 return int(round((phi ** (n + 1) - psi ** (n + 1)) / sqrt5))这个解法的时间复杂度是 O(log n)，因为幂运算可以用快速幂，看起来很美。但它有一个隐患：浮点数精度。n 很小的时候没问题，n 一旦达到 70 甚至 80，float 的精度就撑不住了，round 之后可能差一两个数。LeetCode 70 的 n 不超过 45，用这个公式确实能过，但机考中我不建议用它，因为一旦题目扩大范围，这个公式就会挂。更不要说如果面官想让你讲清楚每一步，公式解法很难延伸出通用的动态规划思路。
如果你对数学比较执着，还有矩阵快速幂解法，时间复杂度 O(log n)，但代码比滚动数组长不少。机考场景下没必要，简单题就应该用最简单直观且不容易出错的方法。
3. 机考现场：怎么快速写出不会挂的答案
3.1 现场解题的三步模板
机考和平常刷题最大的区别是：你没法反复试错，也不能开着题解查。所以在考场上碰到这种题，我建议按一个固定流程走，能在最短时间内减少低级失误。
第一步，读题后先不写代码，在草稿纸上手算 f(1) 到 f(5)。这不需要花多少时间，但它能帮你确认递推关系。算完之后你会发现 1、2、3、5、8，符合斐波那契的形态。
第二步，口头或心里默念状态定义。第 i 阶的方法数是多少？状态转移方程是什么？初始条件是什么？只要这三件事陈述清楚，伪代码基本就出来了。比如：状态 dp[i] 表示爬到第 i 阶的方法数；dp[i] = dp[i-1] + dp[i-2]；dp[1]=1, dp[2]=2。
第三步，直接写滚动数组版本。我个人的习惯是先用 if n <= 2 return n 处理边界，然后写两个变量 prev2、prev1，再循环。整个过程不会超过两分钟。写完之后花三十秒检查循环边界：range(3, n+1) 能不能取到 n？能，因为 range 是左闭右开，n+1 正好取到 n。
3.2 边界条件、溢出与测试点
这道题的边界条件虽然简单，但最容易翻车。第一个边界是 n=1 或 n=2，如果直接进入循环会得到错误结果，或者因为数组长度不够而越界。第二个边界是 n=0，原始题目里 n 是正整数，但如果你把它当作通用工具函数，最好处理成返回 0，很多变体题都会先用 n=0 做测试。
关于整数溢出，C++ 的 int 上限是 2^31-1，也就是 2147483647。爬楼梯第 45 项的答案是 1836311903，正好没超，第 46 项是 2971215073，就超了。LeetCode 70 的 n 约束在 45 以内，所以用 int 没问题，但如果机考题目把 n 改大到 50，C++ 选手就必须用 long long。Python 不用考虑这个问题，任意大整数都能装，这也是很多人机考选 Python 的原因。
我整理了一个自测点清单，写完代码后直接脑内跑一遍：
| 输入 | 期望输出 | 检查点 |
|---|---|---|
| n=1 | 1 | 初始条件 |
| n=2 | 2 | 初始条件 |
| n=3 | 3 | 递推正确性 |
| n=10 | 89 | 多位计算 |
| n=45 | 1836311903 | 大数边界 |
把这些样例快速验证完，基本可以放心提交。
3.3 语言选择与LeetCode环境细节
LeetCode 70 的 Python 接口长这样：
class Solution: def climbStairs(self, n: int) -> int: pass你只需要在类里补全方法即可，不要写 print，也不要在函数外写额外输出。很多刚开始刷题的人喜欢在本地 IDE 里测通后直接把打印语句贴在 LeetCode 上，提交后报格式错误，浪费时间不说，也影响心态。
如果你习惯用 C++，代码结构也很简单：
class Solution { public: int climbStairs(int n) { if (n <= 2) return n; int prev2 = 1, prev1 = 2; for (int i = 3; i <= n; ++i) { int cur = prev2 + prev1; prev2 = prev1; prev1 = cur; } return prev1; } };Java 版本类似，用 int prev2 = 1, prev1 = 2 然后循环。机考时不要在一道题上纠结语言性能，选你平时最熟练的，重要的是写出边界安全、逻辑清晰的代码。
4. 常见问题、变体与经验清单
4.1 五个容易踩的坑
刷题群里经常看到有人在这道题上栽跟头，我把常见的坑整理一下，你对照着看自己有没有踩过。
第一个坑：纯递归不记忆化。这是一道 easy 题，很多人第一反应就是递归，然后 LeetCode 给一个 TLE。原因前面分析过，不重复。
第二个坑：初始条件写错。有人定义 dp[0]=1, dp[1]=1，然后循环从 2 开始，也可以推出正确结果，但如果你理解不清楚 dp[0] 代表什么，很容易把自己绕晕。我更建议直接 dp[1]=1, dp[2]=2，语义清晰。
第三个坑：循环范围写错。写 range(1, n) 或 range(3, n) 都会少算一次。最稳妥的办法是每次写完循环后，用 n=3 手推一遍，看返回值是不是 3。
第四个坑：忽略 n=0。原始题不会出现，但面试官追问时，如果你没有防御性判断，可能暴露边界意识不足。我一般会加上 if n <= 0: return 0，虽然 LeetCode 不要求，但这是个好习惯。
第五个坑：直接抄斐波那契通项公式，没有理解浮点误差。偶尔能过，但换一个测试点就挂。机考里投机取巧的风险太高，不建议。
4.2 从爬楼梯到一类动态规划题
理解了 70 题之后，你会发现它是一大堆动态规划题的原型。比如 LeetCode 746 最小花费爬楼梯，状态转移从单纯计数变成了累加代价，但定义状态和转移方程的思路完全一致。再比如 LeetCode 509 斐波那契数，甚至代码都是同一套滚动数组。
如果你再往前走一步，会看到打家劫舍、最长递增子序列、不同路径这些更复杂的题目。它们的核心依旧没有跳出“状态定义 + 转移方程 + 初始条件”这个框架。所以说，不要在简单题上赶进度，把地基打扎实，后面真的会轻松很多。
还有一个非常有意思的变体：如果每次能爬 1 或 3 阶，方法数又怎么算？答案是 f(n) = f(n-1) + f(n-3)，初始条件也变了。从这个变体你能看出来，公式会随约束变化，但递推思想是稳定的。机考时遇到“爱吃香蕉的狒狒”这类场景化题目，也是在考你能不能把场景抽象成算法模型，而不是背原题。
4.3 刷题节奏：把简单题变成压舱石
最后聊一点刷题节奏。我见过不少同学，机考前夕疯狂刷 hard，结果 easy 题反而没稳住。LeetCode 70 这种题，应该是你的压舱石，不是你的绊脚石。我的建议是：做到一题三解，递归、记忆化、滚动数组都能快速写出来，并且能在十五分钟内把题讲明白。这样不只是在刷题，而是在做一种可复用的思维训练。
如果你准备参加 LeetCode 周赛，这种 easy 题就是用来稳定心态的。周赛前几题常常是经典题的换皮，所以平时刷题时一定要习惯先把题目翻译成熟悉的模型，再动手写代码。基础题稳了，后面遇到 medium 或 hard，你才有时间思考。
我个人在实际机考中的一个习惯是：不管题目多简单，都会先在草稿纸上写下 f(1) 到 f(5)。这个动作花不了十秒钟，但能有效避免边界错误。写完循环后，再默默念一遍 range 的结束值，确认取得到目标 n。这些看起来笨的方法，恰恰是考试时最可靠的保险。爬楼梯这道题的意义，远不止一个 AC，它更像是机考刷题路上的第一块铺路石，帮你在后面的算法森林里找到方向。
