从第一次听到“爬楼梯”这道题到现在我见过太多人把它当成一道“递归入门题”草草刷过。但说实话Leetcode 70这道题的层次远比表面看起来深从暴力递归到矩阵快速幂到通项公式每一层解法都映射着不同的算法思维阶段。这篇日记我打算换一种写法不直接贴最优解而是完整记录我自己从审题、踩坑到逐步优化的一次真实做题过程这套思路对刷其他动态规划题同样适用。1. 审题阶段最容易犯的错把“方法数”当成“步数”题目描述其实很短你正在爬楼梯需要 n 阶才能到达楼顶每次可以爬 1 或 2 个台阶问有多少种不同的方法爬到楼顶。很多第一次刷题的人包括我第一反应是去枚举路径试图把所有走法列出来或者错误地以为这是个排列组合求和的题直接拿阶乘去算。但题目要的是“方法数”不是“最短步数”也不是“步数组合的排列数量”。n 2 时答案是 211 或 2n 3 时答案是 3111、12、21这些基本用例能帮你验证理解是否正确。我曾见过一个朋友在这个题上卡了很久因为他把问题理解成了“每次爬 1 阶或 2 阶一共能产生多少种不同的步长序列”结果枚举到 n 5 就发现数量爆炸思路完全偏了。关键的一步转换在于到达第 n 阶的最后一步只有两种可能要么从第 n-1 阶跨 1 阶要么从第 n-2 阶跨 2 阶。因此到达第 n 阶的方法数等于到达第 n-1 阶的方法数与到达第 n-2 阶的方法数之和。这就是一个标准的斐波那契递推关系和斐波那契数列的区别只是初始值不同。这道题审题的核心收获是动态规划题目的“最后一步”视角往往比“从头枚举”视角清晰得多。每道 DP 题拿到手先问自己“最后一步发生了什么”这比立刻写状态转移方程更可靠。题面上“每次可以爬 1 或 2 个台阶”并不是让你去模拟每一步的选择而是告诉你递推关系的来源。2. 三种必会解法的演进过程从递归到记忆化再到 DP2.1 版本一纯递归思路最简单但效率最差def climb_stairs(n: int) - int: if n 2: return n return climb_stairs(n - 1) climb_stairs(n - 2)这个版本几乎不需要思考直接照搬递推公式。但问题在于重复计算量惊人比如计算 climb_stairs(5) 时climb_stairs(3) 会被计算两次climb_stairs(2) 会被计算三次。整个计算树是接近满二叉树的形态时间复杂度是 O(2^n)。我在本地跑 n 40 时已经明显感觉到卡顿n 45 基本要等好几秒再往上就是灾难。这个版本的唯一价值在于验证递推公式的正确性建议只用它跑 1 到 10 的小规模用例确认结果符合预期后再进入下一步。如果你在 Leetcode 上提交这个版本大概率会收到“Time Limit Exceeded”这是正常的不是代码语法问题而是算法复杂度不过关。2.2 版本二记忆化递归自顶向下第一次引入“状态”def climb_stairs(n: int, memo: dict None) - int: if memo is None: memo {} if n 2: return n if n in memo: return memo[n] memo[n] climb_stairs(n - 1, memo) climb_stairs(n - 2, memo) return memo[n]这个版本的改进很直观把每次算出来的结果存起来下次用到时直接查表。我刚开始用 dict 做 memo后来发现其实可以用列表因为 key 就是连续的整数。时间复杂度从指数级降到了 O(n)空间复杂度是 O(n)。这里有个容易写错的小坑memo 的默认参数不要写成memo{}因为 Python 的默认参数是函数对象级的多次调用同一个函数会共享同一个 dict虽然这道题不影响正确性但在 Leetcode 的判题环境里多个测试用例共用同一个函数对象时可能出现脏数据。我一般写成memoNone在函数内部判断后初始化这样最稳妥。2.3 版本三自底向上的动态规划def climb_stairs(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]这是面试中需要熟练掌握的版本。它的思路完全反过来了不从上往下追问而是从最底层开始逐层往上推。dp[i] 表示到达第 i 阶的方法数初始化 dp[1] 和 dp[2] 之后从 3 开始循环。我个人的做题习惯是二维 DP 至少要在纸上画一遍表格的更新过程一维 DP 也要写出前 5 到 6 项确认没有越界和初始化错误再写代码。这道题的 dp 表非常直观写成数组之后你会发现整个过程就是从前向后滚动计算和手算斐波那契数列没有区别。3. 空间优化与状态压缩把 O(n) 空间压到 O(1)3.1 滚动变量版本的实现细节def climb_stairs(n: int) - int: if n 2: return n prev, curr 1, 2 for _ in range(3, n 1): prev, curr curr, prev curr return curr很容易在这个版本上犯一个隐蔽的错误循环次数和更新顺序。有人会写成for _ in range(n - 2): prev, curr curr, prev curr这个写法本身没错但一旦把 range 的边界算错比如写成 range(n - 1)结果就会差一位。我建议在本地跑 n 5 和 n 6对比结果分别是 8 和 13确认无误再提交。Python 的并行赋值在这个场景下很好用因为它会先计算右边的所有表达式再统一赋值所以不需要引入临时变量。这一点和 C/C 的写法不同用 C 写的时候需要显式写tmp prev curr; prev curr; curr tmp但 Python 里一行就能搞定减少出错机会。3.2 为什么能这样压缩背后的状态依赖关系这个版本能成立的根本原因是计算 dp[i] 时只用到 dp[i-1] 和 dp[i-2]更早的状态完全没有被引用。所以整个 dp 数组在任意时刻只需要保留两个历史值就够了。这个逻辑理解透了以后做 dp[i] f(dp[i-k: i]) 这类题目时就能反应过来用环形数组或队列来优化空间。我在刷题群里见过一种问法“这道题的空间复杂度能不能优化到 O(1)”如果你能解释清楚“因为递推公式的阶数是 2”面试官会觉得你确实理解了状态转移的本质而不是背模板。这个问题的本质是状态依赖范围的宽度不是看 dp 数组的长度。4. 初看意外但值得了解的进阶解法矩阵快速幂与通项公式4.1 矩阵快速幂当 n 足够大到 10 的 18 次方时怎么办如果你只是准备面试矩阵快速幂不是必须的但它能帮你建立“递推关系 矩阵乘法”的看问题方式。斐波那契递推可以用矩阵表示为[n阶方法数 ] [1 1] [n-1阶方法数] [n-1阶方法数 ] [1 0] [n-2阶方法数]也就是说从初始状态出发每乘一次这个 2x2 矩阵相当于向后推进一步。要求第 n 项就是把这个矩阵的 n 次方算出来再乘初始向量。矩阵幂本身可以用二分快速幂加速时间复杂度 O(log n)空间复杂度 O(1)。这个版本的 Python 实现并不难核心是写一个矩阵乘法函数和一个快速幂循环def matrix_multiply(a, b): return [ [a[0][0] * b[0][0] a[0][1] * b[1][0], a[0][0] * b[0][1] a[0][1] * b[1][1]], [a[1][0] * b[0][0] a[1][1] * b[1][0], a[1][0] * b[0][1] a[1][1] * b[1][1]] ] def matrix_power(matrix, power): result [[1, 0], [0, 1]] base matrix while power 0: if power 1: result matrix_multiply(result, base) base matrix_multiply(base, base) power 1 return result常用的矩阵幂优化手段包括二进制拆解指数快速幂这里我直接用了标准写法。如果未来做 Leetcode 的题目时遇到“斐波那契数列的第 n 项n 很大”的变种题直接套这套逻辑就行。4.2 通项公式的 Python 实现陷阱用特征方程解斐波那契递推可以得到通项公式f(n) (phi^n - psi^n) / sqrt(5)其中 phi (1 sqrt(5)) / 2 是黄金比例psi (1 - sqrt(5)) / 2 是它的共轭。理论上这个公式可以直接算出任意项但 Python 里用浮点数实现时n 稍微大一点就会因为浮点精度误差得到错误的整数结果。我测试过 n 70 左右float 的误差就开始影响答案了。如果要硬用通项公式需要借助decimal模块的高精度但这反而削弱了算法本身的价值。我的结论是这道题面试够用的话老老实实写 O(n) 或者 O(1) 空间的滚动变量不用强行秀通项公式。矩阵快速幂可以作为扩展了解写出来加分写不出也不扣分。刷题的核心是能在合理时间内给出正确、稳定的解法而不是所有花活都必须会。5. 边界条件与 Leetcode 提交中的隐性测试点5.1 n 0 和 n 1 这种边界到底该怎么定义Leetcode 原题中n 的取值范围通常是正整数所以 n 0 不一定会测。但如果你在本地测试、或者把这个函数接入到其他系统里必须明确 n 0 时的行为。按数学递推习惯climb_stairs(0) 可以定义为 1表示“已经在楼顶不需要任何动作”也可以定义为 0表示“没有台阶就没有走法”。两种定义在不同题目里都有出现。我建议代码里先判断if n 2: return n这样 n 1 返回 1n 2 返回 2逻辑一致。如果题目改了约束条件比如 n 可以等于 0这一步就得单独处理。5.2 隐含的大整数问题Python 不需要处理但要知道斐波那契数列的增长速度是爆炸式的n 100 时爬楼梯的方法数已经是一个 21 位的超大整数。C 或 Java 里需要用 long long 甚至 BigInteger 才能防溢出但 Python 的整数是任意精度的不需要额外处理直接算就行。这也是 Python 刷题的一个便利之处但反过来也容易让你忽略“其他语言里这题可能存在溢出问题”跟面试官聊天时能主动提一句会更显专业。5.3 为什么有时候 O(n) 的 DP 版本也超时按理说 O(n) 在 Leetcode 上是稳过的但如果你测试的用例是单次大 n比如 n 1000000循环的纯 Python 速度可能只有几万到十几万次每秒取决于运行环境大概会在 0.1 秒到 0.5 秒之间Leetcode 通常不会卡这种级别。但如果遇到循环体内有频繁的函数调用或者用了自定义对象操作速度就会明显下降。碰到极端情况考虑用快速幂或者利用 Python 的functools.lru_cache再配合迭代避免递归深度限制。6. 延伸思考这道题和“不同路径”等常见 DP 题的关联爬楼梯本质上是一个“一维计数类动态规划”问题。它的“最近邻依赖”特点dp[i] 只依赖前两项让解法变得非常简单但这恰恰是很多更复杂 DP 题的基础。Leetcode 62“不同路径”就是一个典型的二维版本机器人从左上角走到右下角每次只能向右或向下走路径总数满足 dp[i][j] dp[i-1][j] dp[i][j-1]。和爬楼梯一样核心都是“最后一步从哪里来”只是状态从一维变成了二维初始化边界处理也更麻烦第一行和第一列都要先置为 1。另一道和爬楼梯相关的经典题是 Leetcode 746“使用最小花费爬楼梯”它把“计数”改成“求最小值”递推公式变成了 dp[i] min(dp[i-1], dp[i-2]) cost[i]。计数变最值这是动态规划最常见的两类问题思维模板完全一致只有转移方程里的运算符从加法变成了 min/max。所以我的建议是不要孤立地刷爬楼梯把它当成一串题目家族的敲门砖。刷完这道题接着去刷 62、70、91解码方法、198打家劫舍你会发现它们的思考路径高度相似都是“定义状态 - 找转移 - 初始化 - 优化空间”的固定套路。等到你练熟了一次能同时做好几道题效率比每天刷一道新题高得多。7. 自己动手做个简单的性能对比测试光看理论分析不够我建议你在本地跑一个简单的性能对比直观看到不同版本的差距。我用的是一段很粗糙的计时代码import time def time_it(func, n): start time.time() result func(n) print(f{func.__name__}({n}) {result}, 耗时 {time.time() - start:.6f}s) # 注意纯递归版 n 40 就已经很慢了 time_it(climb_recursive, 30) time_it(climb_memo, 1000) time_it(climb_dp, 1000) time_it(climb_optimized, 1000)实测下来纯递归跑 n 30 大概 0.1 到 0.2 秒n 40 就可能要 1 到 2 秒。记忆化版本跑 n 1000 几乎是瞬间完成的滚动变量同样迅速。这个对比能直观说明算法优化不是靠魔法只是消灭了重复计算。我在本地还会额外做一个“正确性对比”把滚动变量版本的结果和 DP 版本的结果逐一比对循环 n 从 0 到 1000确认全部一致。这种防御性验证在面试时不一定有时间做但平时刷题养成习惯能帮你减少很多低级的边界错误。8. 一个容易被忽略但面试高频的问题为什么不是“逐步递推”而是“末尾递推”有人会把爬楼梯理解成从第 0 阶开始每次可以加 1 或 2最后得到第 n 阶的走法数。这种“从前往后”的理解不是不行但如果你用 DP 去做会发现状态更新是从小到大本质上还是从末尾往后递推。真正区分这两种视角的地方在于从前往后是模拟选择从后往前是总结规律。模拟选择适合回溯或暴力枚举规律总结适合动态规划和递推。这两者的区别在面试里经常会被追问。比如面试官会问“如果你一次能爬 1、2、3 阶怎么做”这时递推公式就变成 dp[i] dp[i-1] dp[i-2] dp[i-3]本质一样初始化边界从 dp[1], dp[2] 变成了 dp[1], dp[2], dp[3]。如果你能直接从“最后一步”角度解释面对这种扩展题就不会慌。我实际面试中遇到过不止一次类似的变种有的改成“不能连续爬 2 阶”有的改成“某些楼层不能停留”这些本质上都是在训练你对状态转移的敏感度。爬楼梯是最简单的训练场先把这道题吃透后续遇到复杂 DP 才能有条件反射式的“最后一步”直觉。最后分享一个我个人的刷题习惯一道题 AC 之后我不会立刻去刷下一道而是把这道题的所有主流解法都写一遍对比它们的代码量、可读性和运行效率。爬楼梯这道题每个版本我都重写过好几遍直到闭着眼睛都能写出正确的状态转移为止。这种方法看起来很慢但长期下来反而比“一天刷十道题”更扎实。如果你还在为这道题苦恼我的建议就是动手写不要只在脑子里想写坏几次自然就理解了。