1. 题目回顾先把需求搞清楚1.1 题干到底在说什么Leetcode 70题爬楼梯英文名Climbing Stairs是动态规划里最经典的入门题之一。题目描述很简单你正在爬楼梯需要n阶才能到达楼顶每次你可以爬1阶或2阶问有多少种不同的方法可以爬到楼顶。我第一次看这道题的时候以为是个排列组合问题想着不就是走1步和走2步的排列嘛。但真动笔算了一下发现事情没那么简单。n2的时候方法有两种一次跨2阶或者分两次各跨1阶。n3的时候方法有三种111、12、21。n4的时候呢1111、112、121、211、22一共五种。如果你手头有纸笔可以继续列n5的情况会得到8种。细心的朋友可能已经看出来了1、2、3、5、8……这不是斐波那契数列吗没错这道题的答案序列就是斐波那契数列往右平移了一位的变体。但光知道这个还不够我们需要理解为什么它是斐波那契以及如何在Python里高效把它算出来。1.2 这道题为什么值得反复咀嚼爬楼梯在Leetcode上的难度是简单但这道题的历史地位非常高。很多人的动态规划启蒙题就是它面试里也经常作为热身题出现。它几乎涵盖了动态规划的核心思考链路状态定义、转移方程、边界条件、空间优化一个都不少。而且这道题有大量的解法变体从最基础的递归、到记忆化搜索、再到滚动数组DP最后还能延伸到矩阵快速幂和通项公式。每换一种写法你对这个问题以及Python语言特性的理解就深一层。说它是一道顶十道毫不夸张。如果你是刚接触算法题的新手这道题可以作为你理解递归和动态规划的第一块跳板。如果你已经刷过一些题也可以借这道题把自顶向下和自底向上两种思路彻底打通。2. 从暴力递归开始别急着上动态规划2.1 最直觉的写法递归枚举很多教程一上来就给你动态规划的标准解但我建议你别跳步。先写最笨的暴力递归版本对理解问题本质帮助极大。先想想递归的思路爬到第n阶最后一步只有两种可能要么从第n-1阶跨1阶上来要么从第n-2阶跨2阶上来。所以爬到第n阶的方法数 爬到第n-1阶的方法数 爬到第n-2阶的方法数。这就是这道题的核心递推关系。写成代码就是这样def climbStairs(n): if n 1: return 1 if n 2: return 2 return climbStairs(n - 1) climbStairs(n - 2)这个版本极其简单逻辑上完全没毛病。但你把它提交到Leetcode上大概率会收到一个超出时间限制的红色提示。为什么因为它的时间复杂度是O(2^n)n稍微大一点点计算量就爆炸了。2.2 用记忆化去掉重复计算暴力递归慢就慢在重复计算上。我拿n5举例你算climbStairs(5)会去算climbStairs(4)和climbStairs(3)而climbStairs(4)又去算climbStairs(3)和climbStairs(2)。看到了吗climbStairs(3)被算了两次。这不是个例越往下重复越多很多子问题被重复计算了成千上万次。解决办法很直观算过的结果存起来下次直接用。这就是记忆化搜索也叫自顶向下的动态规划。def climbStairs(n): memo {} def dfs(k): if k in memo: return memo[k] if k 1: return 1 if k 2: return 2 memo[k] dfs(k - 1) dfs(k - 2) return memo[k] return dfs(n)加了记忆化之后每个子问题只算一次时间复杂度降到了O(n)。这里我用的是Python字典memo来缓存结果你也可以用列表效果一样的。这个版本是理解自顶向下思想的标准模板值得亲手敲一遍。2.3 重复计算到底有多恐怖在上面的朴素递归版本里调用次数增长得非常疯狂。你如果给纯递归加一个计数器会发现在n30的时候函数已经被调用了166万次左右到n40大概是2亿次n45这个数字已经超过10亿。一台普通电脑跑这个纯递归版本n40就要好几秒n45直接卡到天荒地老。我第一次刷这道题的时候在本地跑了个n50的纯递归版本等了差不多一分钟都没出结果最后只好强制终止进程。这就是指数爆炸的直观感受。而记忆化搜索呢n50只需要几毫秒。差距就在于重复计算被彻底消除了。这个对比能帮你建立起对复杂度分析的敬畏心——刷题的时候先估算时间复杂度再考虑提交可以省掉很多无意义的等待。3. 动态规划正解状态、转移、边界三件套3.1 状态定义和转移方程推导动态规划的核心就三件事状态定义、转移方程、边界条件。爬楼梯这道题正好把这三个要素都讲明白了。先定义状态设dp[i]表示爬到第i阶楼梯的方法数。然后找转移关系要到达第i阶最后一步要么从第i-1阶跨上来要么从第i-2阶跨上来。所以dp[i] dp[i-1] dp[i-2]。这就是状态转移方程与斐波那契数列的递推式完全一致。边界条件也清晰第1阶只有1种方法就是跨1阶第2阶有2种方法1阶1阶或者直接跨2阶。所以dp[1] 1dp[2] 2。有了状态定义和转移方程代码其实就水到渠成了。这里我多说一句不是所有动态规划题的边界条件都这么直观。有些题需要做虚拟哨兵比如dp[0] 1这种技巧才能在递推时不越界。爬楼梯这题很良心不需要这些花活但对这个边界的处理方式值得记下来后面刷类似的题可以直接套用。3.2 标准Python实现数组DP自底向上的动态规划也叫填表法从小的子问题开始一步步算到大问题。Python代码长这样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]这段代码有几个容易踩的坑我一个个说。首先是边界判断if n 2直接返回n这个一定要写在最前面否则n1的时候dp[2]就下标越界了。其次是dp列表的长度我写成(n1)这样下标从0到n都能用dp[0]虽然用不上但占个位置能避免很多索引混乱。循环从3开始到n结束Python的range左闭右开所以写range(3, n1)。如果写错成range(3, n)n5的时候只会算到dp[4]结果就是错的而且很难一眼发现。这种边界错误用print大法调试一下就能看出来但提前养成习惯会更省事。3.3 空间优化滚动数组上面的数组DP版本时间复杂度O(n)空间复杂度O(n)。但有个很容易发现的规律dp[i]只依赖dp[i-1]和dp[i-2]之前的dp[0]到dp[i-3]全都不再需要了。既然如此我们没必要用一个长度n1的数组只需要两个变量倒腾一下就行了。这就是滚动数组优化把空间复杂度从O(n)降到了O(1)。代码也很简洁def climbStairs(n: int) - int: if n 2: return n a, b 1, 2 for _ in range(3, n 1): a, b b, a b return b这里的核心就是Python的多变量赋值特性a, b b, a b会先计算右边的值再同时赋值给左边的变量所以不需要临时变量中转。如果你用其他语言写一般得写成temp a b; a b; b tempPython的这一行赋值确实省事不少。我刷完这题之后有段时间写动态规划题都会下意识地想一下状态转移只用到了前面几个状态能不能滚动这个习惯帮我省了不少内存在后面的打家劫舍买卖股票等题目里都用得上。4. 不止一种解法顺带把技术债还了4.1 通项公式解法既然答案就是斐波那契数列的变体那我们能不能直接用斐波那契通项公式算数学上当然可以。斐波那契数列有一个用黄金分割数表示的闭式解爬楼梯问题套进去一样能用。Python里可以这样写def climbStairs(n: int) - int: import math sqrt5 math.sqrt(5) phi (1 sqrt5) / 2 psi (1 - sqrt5) / 2 return int((phi ** (n 1) - psi ** (n 1)) / sqrt5)这个版本的时间复杂度是O(log n)因为主要开销在幂运算上。但实际跑起来由于浮点数精度问题n很大的时候可能出现误差。Leetcode这题n的上限是45误差还不至于翻车但刷题心态上我更推荐用整数运算的DP解法毕竟算法题的核心是考察思维不是炫数学技巧。4.2 再进一步矩阵快速幂如果你还想把复杂度往上卷可以用矩阵快速幂把时间压到O(log n)同时保持整数精度。思路是把递推关系写成矩阵形式然后对矩阵做快速幂运算。def climbStairs(n: int) - int: if n 2: return n def mat_mul(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 mat_pow(M, k): result [[1, 0], [0, 1]] while k: if k 1: result mat_mul(result, M) M mat_mul(M, M) k 1 return result base [[1, 1], [1, 0]] res mat_pow(base, n - 1) return res[0][0] res[0][1]说实话这题用矩阵快速幂属于杀鸡用牛刀但作为一个拓展练习它能帮你把矩阵运算和二分幂这两个知识点一起复习了。面试的时候如果能把这道简单题讲到矩阵快速幂这个深度给面试官的印象会很不一样。4.3 同类题与变种题目一览爬楼梯有很多变种刷完这道之后趁热打铁做做下面这些题性价比很高Leetcode 746 使用最小花费爬楼梯在转移方程里加了一个cost数组状态变成到达当前阶梯的最小花费需要用min而不是sum。Leetcode 509 斐波那契数本质就是裸的斐波那契可以用它来对比爬楼梯的边界差异。Leetcode 1137 第N个泰波那契数递推式变成三项求和滚动数组要从两个变量变成三个变量。Leetcode 70变种一次可以爬1、2、3阶递推方程变为dp[i] dp[i-1] dp[i-2] dp[i-3]边界条件也要重新推导。这种打怪升级式的刷题方式比漫无目的地刷题效率高很多。学到一个套路马上在五六个相关题目里验证记忆会非常牢固。5. 刷题环境与Python运行配置经验5.1 本地怎么写怎么跑刷题最常见的场景是网页上直接写代码但本地跑一遍往往能看到更多细节比如实际运行时间、递归调用次数、print调试输出等。所以我强烈建议在本地配好Python环境再刷题。如果你新买的电脑还没装Python去官网下载安装包安装的时候记得勾选Add Python to PATH这一步很多新手会漏掉。装完在终端输入python --version能输出版本号就说明环境OK了。编辑器方面我见过VSCode党和PyCharm党各占半壁江山。VSCode轻量配置Python插件之后按F5就能调试PyCharm更重但对代码补全和静态检查的支持更到位适合常驻写项目的人。不管用哪个核心就一件事能写.py文件、能一键运行、能打断点调试。踩过坑的朋友应该懂环境配置这块有一堆细节需要注意比如解释器选错了、插件没生效、路径带中文导致的诡异报错。5.2 用Python自带语法做自动化验证LeetCode网页上提交一次就能看到结果但本地验证有时候更快。我推荐你在本地写好测试用例用assert断言来批量验证def climbStairs(n: int) - int: a, b 1, 2 for _ in range(n - 1): a, b b, a b return a # 手工熟悉的几组结果 test_cases [(1, 1), (2, 2), (3, 3), (4, 5), (5, 8), (6, 13)] for n, expected in test_cases: assert climbStairs(n) expected, fn{n}, got{climbStairs(n)}, expect{expected} print(all test passed)assert断言的好处是出错时能立刻定位到具体是哪个n出了问题。我在刷题的时候这种测试脚本伴随了我很久。等n比较大的时候还可以用循环批量验证规律比如n从1到20看输出是不是1、2、3、5、8、13……这个数列一眼就能看出自己的实现有没有跑偏。5.3 数据规模与运行时间实测我针对几种解法做了个小实验在本地分别跑不同n值记录了大致耗时。纯递归版在n30就已经需要能感知的等待n35就开始让人不耐烦n40基本没法用。而记忆化搜索和DP版本跑n45题目上限都是毫秒级体感上几乎测不出差别。这组对比很有教学意义很多时候能跑通和能通过评测是两回事约束条件决定了你需要什么量级的算法。爬楼梯n的范围小DP绰绰有余但要是题目改成n最大10的18次方那你就得祭出矩阵快速幂了。还有一个细节值得提Python的整数是任意精度的不会像C或Java那样在n47左右出现整数溢出。Leetcode这题的答案在n45时还没超过int范围但刷其他题的时候Python的这一特性会减少很多烦心事。6. 常见问题与踩坑实录6.1 高频报错速查表我整理了一份这个小题目里最容易踩的坑都是实战里真实出现过的不是网上抄来的错误类型典型表现原因与解法下标越界IndexError: list index out of rangen 2时直接return n别走循环死循环没有任何输出递归没有终止条件检查base case答案偏小n4输出4而不是5range终点写成了n-i边界搞错答案偏大n4输出8而不是5循环次数多了一次range起点写错超时提交提示Time Limit Exceeded用了纯递归改成DP或记忆化输出浮点数5.0而不是5用了通项公式但忘了取整这里最坑的是答案偏大这种情况。我第一次写滚动数组版本的时候把循环写成了for _ in range(2, n)结果n4输出了8还困惑了好一会儿。后来打印每一轮a、b的值才发现循环多跑了一次。6.2 为什么明明逻辑对Leetcode不认很多人会碰到这种场景本地运行结果全都正确提交到Leetcode却报错。除了上面说的边界条件之外还有几种可能。第一函数签名不匹配。Leetcode给的代码模板里有个class Solution你需要在类里面定义方法而不是在文件外层写一个独立函数。很多新手在本地习惯了py脚本直接写函数复制过去的时候忘了缩进对齐就会报编译错误或者找不到方法。第二返回值类型不对。如果题目要求返回int你return了一个字符串或者浮点数测试用例就会很奇怪地挂掉。第三用了不推荐的全局变量。有些跨测试用例的全局状态没有清理导致第二次调用函数时结果不对。爬楼梯这题一般不涉及但养成函数内部尽量自包含的习惯很重要。6.3 我自己总结的动态规划做题口诀刷了上百道动态规划题之后我总结了一套自己的分析流程每次拿到DP题都按这个顺序走一遍基本不会乱。第一步把题目用变量描述出来明确状态是什么。爬楼梯里状态就是在第i阶。第二步假设我已经知道了子问题的答案考虑最后一步能怎么走从而得到递推关系。第三步确定初始值和边界条件手算前几项验证递推式是否正确。比如推导出dp[i] dp[i-1] dp[i-2]之后拿n3去验证dp[3]应该等于dp[2] dp[1] 2 1 3手动枚举一遍确实也是3思路正确。第四步考虑能不能空间优化。看一下转移方程依赖了几个历史状态只保留需要的变量。这个方法在爬楼梯这道题上得到了充分实践。你如果能严格按照这个流程把这道题分析透后面接触更复杂的DP题时会发现内核其实都一样。最后再分享一个小技巧Leetcode刷题不要只盯着通过率学会看官方题解和讨论区里的高赞答案往往能发现更优雅的解法。拿爬楼梯这道题来说有人用一行数学公式解决有人把矩阵快速幂写得非常精练甚至有Python选手用reduce加列表推导一行搞定滚动数组。刷题不只是为了过测试更是为了开阔思路。每次看到比自己更妙的写法就复制粘贴到本地跑一跑研究透彻慢慢就会形成自己的武器库。