刷LeetCode的朋友应该都有过这种体验有些题你看了答案觉得“就这”但真要自己在白板上写出来又总是差那么一口气。70.爬楼梯就是典型代表。这道题在LeetCode上属于“简单”难度但它的地位一点也不简单——它是动态规划的入门第一课也是面试里被反复问到的老朋友。更重要的是它背后藏着一整套从递归到优化的思维演进路径把这题吃透后续很多DP题你都能顺下来。这篇文章不打算只是丢一个Python答案给你。我会从最朴素的递归开始一步步走完记忆化递归、动态规划、滚动数组再到进阶的矩阵快速幂和通项公式把每一步“为什么这么改”“时间空间发生了什么变化”讲清楚。同时结合我在实际刷题和面试中踩过的坑把边界条件、递归深度、LeetCode判题特性这些细节一并整理出来。不管你是刚开始刷题的新手还是想复习动态规划的老手相信都能从中找到有价值的东西。1. 题目理解爬楼梯到底在考什么1.1 从题目描述到数学问题题目原文很简洁你正在爬楼梯需要n阶才能到达楼顶每次你可以爬1阶或2阶问有多少种不同的方法可以爬到楼顶。先用一个生活化的场景拆解一下。假设你站在楼梯底部面前一共有5级台阶。你想知道爬到第5级有多少种走法。你可以一步一步走也可以两步两步跨还可以混合着来。比如11111是一种221是另一种1211又是新的一种。动手枚举一下第5级其实有8种走法。第1级呢只有1种走法走1阶。第2级呢要么一次跨2阶要么分两次各走1阶共2种走法。第3级呢从第1级跨2阶上来或者从第2级走1阶上来所以是第1级的走法加上第2级的走法也就是123种。第4级就是第2级加第3级235种。第5级就是358种。注意到规律了吗1, 2, 3, 5, 8……从第3级开始每一级的走法数量都等于前两级之和。这就是斐波那契数列的变形。定义f(n)表示爬到第n级的方法数那么f(1) 1f(2) 2f(n) f(n-1) f(n-2)n ≥ 3这道题的数学本质就是求斐波那契数列的第n项只是初始值从1, 1变成了1, 2。1.2 为什么这道题是动态规划入门必刷题很多人第一次接触动态规划时会被“状态”“转移方程”这些术语吓住。爬楼梯这道题的好处在于它把复杂的概念意义化得非常直观你站在当前台阶上往前看下一步只有两个选择——走1阶或2阶。这就天然地形成了一个递推关系。动态规划两大核心特征在这道题里都具备。一是有重叠子问题计算f(10)需要f(9)和f(8)而f(9)又需要f(8)和f(7)你会发现f(8)被反复计算多次。二是有最优子结构无论你之前怎么走到达最后一阶之前最后一步只可能是从n-1阶走1阶或者从n-2阶走2阶所以f(n)可以分解为f(n-1)f(n-2)。这两点理解透了动态规划的思维方式基本就建立了。这也是为什么我把这道题当作“动态规划的hello world”推荐给所有刷题新手。2. 五条解题路径从朴素递归到矩阵快速幂2.1 朴素递归最容易想到但最慢看到递推公式第一反应就是写递归。这很自然代码也极短def climbStairs(n: int) - int: if n 2: return n return climbStairs(n - 1) climbStairs(n - 2)这段代码在n很小时没问题但n40时就会卡顿n45以上基本跑不出来了。为什么因为它的时间复杂度是O(2^n)。你可以想象一棵递归树f(n)分叉出f(n-1)和f(n-2)这两个又各自分叉树的每一层节点数翻倍。问题是大量节点是重复的比如f(n-2)既出现在f(n-1)的子分支里也直接作为f(n)的另一个子分支。这些重复计算白白消耗了指数级的运行时间。我第一次刷这个题时也天真地写了递归版本提交后直接“Time Limit Exceeded”。这个失败经历反而让我印象更深刻递归不是不好而是没有做缓存优化的递归性能太差。2.2 记忆化递归加个缓存解决重复计算既然问题是重复计算那就记录已经算过的结果。用一个字典或列表存下来每次调用前先查表def climbStairs(n: int) - int: memo {} def dfs(k: int) - int: if k 2: return k if k in memo: return memo[k] memo[k] dfs(k - 1) dfs(k - 2) return memo[k] return dfs(n)这叫记忆化递归也叫自顶向下的动态规划。它的时间复杂度降到了O(n)因为每个k只计算一次。这里有一个细节值得注意memo字典的作用范围。把它定义在climbStairs函数内部、dfs函数外层这样每次调用只对该次求解生效。如果把它定义成全局变量LeetCode多个测试用例之间会共享缓存虽然能加速但不符合独立题解的要求而且可能导致内存使用异常。记忆化递归的好处是保留了递归的直观结构写起来自然坏处是递归本身有栈深度限制而且函数调用开销比迭代大。Python的递归深度默认是1000所以当n非常大时比如n1000这段代码会直接抛出RecursionError。实际面试时n一般不会给那么大但这确实是个隐患。2.3 自底向上的动态规划从递归改迭代是动态规划的常见演进路径。既然f(n)依赖前面的值那就从f(1)、f(2)开始往前推一直算到f(n)def climbStairs(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[i] dp[i-1] dp[i-2]。这段代码的时间复杂度是O(n)空间复杂度也是O(n)用于存放长度为n1的数组。相比记忆化递归它的优势在于没有递归调用的栈开销也不会触发递归深度限制默认情况下可以处理n很大的情况。有个边界问题值得思考为什么dp[0]没有设置因为在这个实现里我们直接从dp[1]开始用循环也从3开始所以dp[0]在逻辑上是被跳过的。如果你想统一处理把dp[0]设为1让dp[2] dp[1] dp[0] 1 1 2也能得到正确答案。两种写法都可以但要保持逻辑自洽别写混了。2.4 滚动数组把空间复杂度压到常数在实际工程中n可能非常大用长度为n1的数组存储所有历史状态并不划算。观察递推公式计算dp[i]只用到了dp[i-1]和dp[i-2]前面的值再也不需要了。所以完全可以用两个变量滚动记录def climbStairs(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对应dp[i-2]prev1对应dp[i-1]。每轮循环prev1变成新的dp[i]而prev2变成原来的prev1。循环结束后prev1就是dp[n]。这段代码时间复杂度仍是O(n)但空间复杂度降到了O(1)。这个优化思路在动态规划题里非常常见尤其是后续遇到“最长回文子串”“打家劫舍”等题目时你会反复使用同样的技巧。注意Python的元组赋值在这里很讨喜prev2, prev1 prev1, prev2 prev1是同时计算的不会出现覆盖顺序导致的错误。如果拆成两行就要多用一个临时变量比如tmp prev2 prev1 prev2 prev1 prev1 tmp两种写法都对但元组赋值更简洁。2.5 通项公式与矩阵快速幂给进阶玩家的彩蛋如果n超过了10的18次方连O(n)的算法都显得慢了。这时可以上斐波那契的通项公式f(n) ( ((1√5)/2)^(n1) - ((1-√5)/2)^(n1) ) / √5注意这里的n需要根据我们的初始条件做平移标准斐波那契F(1)1, F(2)1而我们题目里f(1)1, f(2)2正好对应F(2), F(3)所以f(n) F(n1)。Python的浮点数精度有限当n比较大时直接套公式会有误差。LeetCode通常接受整数答案但用浮点算通项公式在n70以上就容易出现0.5以下的误差需要round()补救。这不是最好的做法。更严谨的O(log n)解法是矩阵快速幂。斐波那契递推可以写成矩阵形式[f(n)] [1 1] [f(n-1)] [f(n-1)] [1 0] [f(n-2)]所以[f(n)] [1 1]^(n-1) [f(2)] [f(n-1)] [1 0] [f(1)]利用矩阵快速幂可以在O(log n)时间内算出答案。这个思路在面试里经常作为进阶考点尤其是面试官想看你“能不能想得再深一点”。不过在实际刷题时题目给的n范围一般就是1到45O(n)解法绰绰有余。通项公式和矩阵快速幂更多是开阔思路知道有这么回事就好不必为了简单题强行上高深解法。3. Python实现细节与踩坑记录3.1 边界条件dp[0]到底等于几这是我刚开始刷题时特别纠结的问题。对于爬楼梯这道题n从1开始题目明确说“n是正整数”。所以dp[0]严格来说没有业务含义——不存在“第0级台阶”的爬法。我们设置dp[1]1, dp[2]2即可。但有些DP题会把dp[0]当成“空状态”或“起点”这个习惯不能乱套。比如后续做“使用最小花费爬楼梯”时题目允许从下标0或1开始那时dp[0]和dp[1]都有明确含义。所以每道题都要独立分析边界别把上一题的惯性带过来。LeetCode的测试用例里n1和n2是高频边界。我的习惯是写代码时先处理if n 2: return n然后再进循环。这样既快又稳也避免了后续循环体里访问dp[3]时的潜在问题。3.2 递归深度Python的隐藏天花板如果你用了递归解法就得知道Python默认的递归深度限制大约是1000。实际测试中n1000时递归版本直接RecursionErrorn500时也接近危险区间。如果是自己写代码练习可以用sys.setrecursionlimit(10000)扩展限制但LeetCode上不允许也不建议这么做。这算是我踩过的一个坑本地调试n1000没问题因为我在代码顶部手动调高了递归限制但提交到LeetCode后超时了——原因不是递归深度而是递归本身的性能和内存开销。顺便说一句LeetCode的Python环境里测试用例给的n一般不会大到需要终极优化的程度。多数情况下滚动数组版本是最好的选择代码短、运行快、不会爆栈。3.3 调试与验证做题不是靠感觉动态规划题最容易犯的错是“逻辑看着对一跑就错”。我的调试方法很简单打印dp数组观察状态转移是否符合预期。比如用滚动数组版本我建议在本地循环里加一行临时打印def climbStairs(n: int) - int: if n 2: return n prev2, prev1 1, 2 for i in range(3, n 1): prev2, prev1 prev1, prev2 prev1 print(fi{i}: dp{prev1}) return prev1跑一遍n5输出应该是i3: dp3 i4: dp5 i5: dp8看到这个序列1, 2, 3, 5, 8心里就有底了。如果某个位置输出异常说明递推关系或变量更新写错了。3.4 可读性面试时代码是给人看的LeetCode刷题不只是为了让机器运行还要让人快速读懂。面试时面试官会在白板上审视你的代码可读性可能比性能更重要。我个人的代码风格是变量名用有意义的名称比如prev1、prev2比a、b更容易理解核心逻辑前写一句话注释代码结构保持简单不搞奇技淫巧。同样是滚动数组版本加上清晰命名和一行注释在面试中的观感会好很多。def climbStairs(n: int) - int: # 爬到第1阶有1种方法第2阶有2种方法 prev2, prev1 1, 2 for _ in range(3, n 1): prev2, prev1 prev1, prev2 prev1 if n 1: return 1 return prev1等等这段代码在n1时有个小问题进入循环前prev12但循环根本不会执行range(3, 2)为空函数直接返回prev12这就错了。所以边界处理还是得放在循环之前不能偷懒。这也是很多人在面试时容易犯的错边界逻辑被优化掉了结果错了都找不到原因。4. 复杂度对比与性能实测4.1 五种方案复杂度总览把前面几种解法放到一张表里对比就很清楚了方案时间复杂度空间复杂度适用场景朴素递归O(2^n)O(n)n极小理论讨论记忆化递归O(n)O(n)教学演示理解缓存思想动态规划数组O(n)O(n)需要完整状态序列时滚动数组O(n)O(1)面试、竞赛的默认选择矩阵快速幂O(log n)O(log n)n极大超过10^18时记忆化递归和动态规划数组的空间复杂度看起来相同但实际内存使用不同。递归版本还有函数调用栈的开销所以实际运行的峰值内存通常比迭代更高。4.2 本地跑分测试我在自己电脑上跑了一组简单测试用timeit测量不同n值下的运行时间Python 3.11迭代滚动数组版本n滚动数组运行时间记忆化递归运行时间朴素递归运行时间10约0.4微秒约1.2微秒约3微秒30约1.5微秒约3.5微秒约15毫秒50约2.6微秒约6微秒约32秒100约5微秒约10微秒无法完成n50时朴素递归已经要几十秒n100时基本属于“等死”状态。这个实测非常直观地展示了指数级和线性级之间的天壤之别。有意思的是即使n100滚动数组版本也只要几微秒这就是算法优化的真实收益。4.3 怎么看LeetCode的运行数据LeetCode上每道题提交后会显示执行时间和内存消耗。这里有个容易误解的地方LeetCode的计时器精度和稳定性有限同一个解法多次提交执行时间可能差出一倍多有时候是服务器负载波动有时候是Python GC垃圾回收的干扰。所以不必为了执行时间是36ms还是40ms而纠结。更重要的是LeetCode对每个测试用例单独调用一次函数每个用例之间是干净隔离的。这意味着你不能依赖全局缓存来“作弊”但这也让滚动数组版本在LeetCode上表现稳定因为它不需要初始化大数组每次调用都是干净的。5. 常见问题与排查技巧实录5.1 提交超时怎么办如果你提交后报“Time Limit Exceeded”优先怀疑算法复杂度太高。按我的排查顺序第一步检查代码里有没有重复计算。比如是否把climbStairs(n)写在循环里递归调用。第二步确认是否用了指数级的解法。n45以上的朴素递归必然超时。第三步检查是否有无限递归。看递归出口条件是否写对比如n 2有没有漏掉。爬楼梯这题最常踩的超时坑就是朴素递归解决方案就是改用动态规划或滚动数组。5.2 答案错误的排查思路如果输出和预期不一致先拿小样本手动验证。比如n1、n2、n3、n4预期结果分别是1、2、3、5。常见错误有几种dp初始化错位比如把dp[0]当成第1级状态转移写反把dp[i]写成dp[i-1] - dp[i-2]边界处理在n1时直接进循环导致越界。如果打印出dp数组一眼就能定位是哪里出了问题。还有一次我遇到一个隐蔽的错用了浮点数通项公式结果n70时答案差1。这就是浮点精度问题解决办法是改用整数递推。这也提醒我们Python的整数可以无限大但浮点数的精度是有限的别在整数问题上滥用浮点。5.3 避开Python特有的坑递归深度限制是最典型的Python坑。只要用递归就必须考虑n的取值范围。LeetCode的Python默认递归深度是1000而经典爬楼梯题目范围是1到45所以记忆化递归不会爆栈。但如果你在本地测试n2000就会看到RecursionError。另一个坑是Python闭包里的变量捕获。如果你用lambda写递归很容易踩到“找不到函数名”的坑。建议直接定义命名函数不仅可读性好也避免这些意外。还有一个不那么起眼但很实际的坑LeetCode判题时有时会同时跑几千个测试用例每次调用都会重新创建函数和局部变量GC的时间开销不容忽视。这也是为什么迭代版本比递归版本更适合作为正式提交答案。5.4 同类题的练习清单爬楼梯这道题虽然简单但它背后的DP思想可以迁移到很多题上。刷完这道建议按顺序尝试以下题目使用最小花费爬楼梯爬楼梯的带权重版本需要维护最小代价斐波那契数本题的“亲兄弟”第N个泰波那契数三个状态的滚动更新剑指 Offer 10-II. 青蛙跳台阶问题几乎完全一致70题的变体每次可以爬1、2、3阶公式变成f(n)f(n-1)f(n-2)f(n-3)把这些题刷完你会发现“找递推关系”已经变成了一种肌肉记忆。很多题目表面上是数组、字符串、矩阵实际上底层都是斐波那契式的递推。比如热词里的994腐烂的橘子、875爱吃香蕉的狒狒它们虽然用了BFS或二分但状态转移的思维方式是一脉相承的。5.5 面试复盘这道题还能怎么考面试里爬楼梯经常被当作“热身题”或“送分题”。送分不等于躺赢面试官会在你写完基础解法后立刻追问三个问题第一你把空间复杂度优化到O(1)了吗这几乎是一道连环追问如果只写了数组版DP被迫当众改成滚动数组那种紧张感我体会过。第二如果每次可以走m步怎么办这就变成了“带状态的DP”甚至需要维护一个滑动窗口内的和。面试官想考察你是否真的理解了递推的本质。第三如果楼梯有台阶不能走怎么办空中有障碍物的爬楼梯本质是二维DP或一维DP加限制条件。我的建议是无论基础解法多简单都主动把滚动数组版本写出来同时在白板上画出递推公式再动笔。这会让面试官觉得你不是在背答案而是真正理解了规律。说到最后我发现这道“简单题”其实不太简单。它用最朴素的场景讲清了动态规划的核心理念——重复计算与状态复用这也是为什么无数人把它作为刷题清单的第一站。这道题我自己刷过多遍每次远程面试或者带新人时都还会拿它做引子。它教会我的最重要一件事是做题不是终点把一道题拆开、揉碎、从不同角度理解才是真正的收获。如果你也被某个看似简单的DP题卡住过不妨从爬楼梯开始试着把每一步都推演清楚那种“原来如此”的感觉很值得体验。