机考刷题到第 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 阶这是一个明确的约束。举个例子n3 时有三种方法1111221。为什么不是 111 和 21 和 12 后两种算不同因为题目说“不同的方法”顺序不同也算不同所以 12 和 21 是两种独立方案。如果你手算前几项会得到一个非常眼熟的数列n123456方法数1235813这不就是去掉第一项的斐波那契数列吗很多人看到这里就开始背公式但机考不只看你最终答案对没对更看你写代码的过程是否可靠。如果你只是记了一个斐波那契公式遇到变体题比如从“每次爬 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)。每次调用都会分裂成两个子问题形成一个巨大的递归树。n45 时计算量是一个天文数字。递归栈的深度也会达到 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) 本质上就是斐波那契数列的第 n1 项所以也可以用斐波那契通项公式直接求。公式长这样F(n) ((1 √5)/2)^n - ((1 - √5)/2)^n) / √5对应到爬楼梯答案就是 F(n1)。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 甚至 80float 的精度就撑不住了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, n1) 能不能取到 n能因为 range 是左闭右开n1 正好取到 n。3.2 边界条件、溢出与测试点这道题的边界条件虽然简单但最容易翻车。第一个边界是 n1 或 n2如果直接进入循环会得到错误结果或者因为数组长度不够而越界。第二个边界是 n0原始题目里 n 是正整数但如果你把它当作通用工具函数最好处理成返回 0很多变体题都会先用 n0 做测试。关于整数溢出C 的 int 上限是 2^31-1也就是 2147483647。爬楼梯第 45 项的答案是 1836311903正好没超第 46 项是 2971215073就超了。LeetCode 70 的 n 约束在 45 以内所以用 int 没问题但如果机考题目把 n 改大到 50C 选手就必须用 long long。Python 不用考虑这个问题任意大整数都能装这也是很多人机考选 Python 的原因。我整理了一个自测点清单写完代码后直接脑内跑一遍输入期望输出检查点n11初始条件n22初始条件n33递推正确性n1089多位计算n451836311903大数边界把这些样例快速验证完基本可以放心提交。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) 都会少算一次。最稳妥的办法是每次写完循环后用 n3 手推一遍看返回值是不是 3。第四个坑忽略 n0。原始题不会出现但面试官追问时如果你没有防御性判断可能暴露边界意识不足。我一般会加上 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它更像是机考刷题路上的第一块铺路石帮你在后面的算法森林里找到方向。