今天是代码随想录算法训练营的第三十七天打卡记录里排在列表上的是三道动态规划入门题509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯。这三题在难度上都不高甚至被很多老手称为“送分题”但真正刷下来你会发现它们才是理解整个动态规划体系最重要的三块基石。状态定义、递推公式、初始化、遍历顺序、打印dp数组验证这五步被卡哥反复强调的“动规五步曲”在这三题里全部都能跑一遍而且是成本最低的一遍。如果你刚开始接触动态规划这三题建议不要急着看题解先自己硬写写不出来再对照如果你已经刷过几道DP题也可以借这三题把自己脑子里的“套路”重新校准一遍。今天这篇就把三道题放在一起讲重点是公式背后的为什么、初始化里的坑、以及我怎么排查那些新手必踩的错误。1. 为什么DP入门要先刷这三道题1.1 斐波那契数一个朴素的递推骨架509题要求计算第n个斐波那契数递推关系直接写在题目里F(n) F(n-1) F(n-2)。很多第一次接触动态规划的人会觉得这题没有“动态”的感觉因为公式都给你了照抄就行。但恰恰是这个最朴素的骨架能帮你看懂递推的本质一个问题的答案只依赖前两个子问题的答案。你要是用暴力递归去写会发现重复计算量非常大但如果你把每一步算出来的结果存下来后面的计算就是O(n)级别的。我经常跟周围的朋友说斐波那契数就是动态规划的“Hello World”。它没有任何额外干扰项没有权重、没有选择、没有边界判断只有递推。你在这个题上把“用数组存中间结果”这个思维练熟后面所有的DP题都建立在这个基础上。1.2 爬楼梯递推关系变成计数问题70题爬楼梯问的是每次能爬1阶或者2阶爬到第n阶有多少种方法。如果你的眼睛只盯着数字会觉得它和斐波那契一模一样无非是dp[i] dp[i-1] dp[i-2]初始条件换成dp[1]1、dp[2]2。但这题的真正价值在于意义上的转变。斐波那契数里F(5)只是第5个数而爬楼梯里dp[5]是有具体含义的走到第5阶台阶一共有多少种走法。为什么能加起来因为最后一步如果跨1阶那前面一定是走到第4阶最后一步如果跨2阶那前面一定是走到第3阶。“最后一步跨1阶”和“最后一步跨2阶”是两个互斥的事件互斥的事件总数直接相加这就是最基础的计数原理。把这个理解了你以后遇到路径计数、方案数问题就不会傻傻地去背公式而是会问自己最后一步有哪些选择每个选择对应的子问题是什么这两个子问题的答案能直接相加吗这一套问法就是从爬楼梯这题长出来的。1.3 最小花费爬楼梯从“有多少种”到“最少花多少”746题是在爬楼梯的基础上引入了cost数组每个台阶向上爬需要支付对应的体力值可以从下标0或1开始问爬到楼顶的最小花费。注意这里有个容易忽略的地方——楼顶不是最后一个台阶而是越过最后一个台阶之后的那个位置所以如果数组长度是n最终目标是站在第n阶也就是越过cost[n-1]。这一题把动态规划从“计数”带到了“最优化”。递推公式里不再只有加号而是出现了min站在第i阶的最低花费等于min(从第i-1阶爬上来的花费从第i-2阶爬上来的花费)。这正好对应了DP里的核心目标在多个可行方案里找最优。更重要的是它引出了“起点的选择问题”。题目允许从0或1开始而且起步不需要花钱这是一个非常巧妙的设定。很多人在初始化时把cost[0]和cost[1]算进去结果答案比正确答案大了一圈。这种“状态定义和初始条件互相打架”的感受只有亲自写错一次才体会得最深。1.4 动规五步曲三道题共用的一套框架代码随想录里反复强调的动规五步曲放到这三题上可以整理成一张表确定dp数组以及下标的含义dp[i]到底表示什么是第i个数、第i阶的方案数还是站在第i阶的最小花费。确定递推公式这一步要回答“dp[i]由哪些更小的子问题组成”。dp数组如何初始化边界值是递推的起点写错一步全盘皆输。确定遍历顺序通常一维DP都是从前往后但你要知道为什么是从前往后。举例推导dp数组小规模数据手算一遍再和代码输出对照。这三道题恰好能把这五步逐一落实。很多人觉得五步曲是废话直到刷到二维DP、背包问题、编辑距离时才后悔当初没把这种“先想清楚再写代码”的习惯养成。相信我花时间在这三题上把五步走踏实比急着刷三十道难题有用得多。2. 核心细节解析状态定义、递推与初始化2.1 dp数组的含义先抠字眼再动手我见过太多人做DP题上来先写for循环写到一半才发现dp[i]的含义没想清楚。第一题斐波那契数dp[i]就是第i个斐波那契数这没歧义第二题爬楼梯dp[i]表示爬到第i阶台阶的走法总数对象是“台阶”第三题最容易出问题dp[i]到底表示“站在第i阶时已经花掉的最小体力”还是“从第i阶出发继续爬到楼顶还要花的最小体力”两种定义都能做但递推和初始化完全不同。我建议新手统一采用“站在第i阶时已经花费的最小体力”这个定义。这样一来到达楼顶越过最后一个台阶的状态就是dp[n]n等于cost数组长度。递推时既然你站在第i阶说明你上一步要么从第i-1阶爬过来要么从第i-2阶爬过来所以dp[i] min(dp[i-1] cost[i-1], dp[i-2] cost[i-2])。这里的cost[i-1]和cost[i-2]分别表示从第i-1阶和第i-2阶向上爬的代价。很多题解喜欢把dp[i]定义成“爬到第i个楼梯的最小花费”然后最后返回min(dp[n-1], dp[n-2])之类的也能对但容易把自己绕晕。我个人的习惯是凡是边界稍微有点弯的题先把“站在哪里”、“目标在哪里”写在注释里再开始写代码。2.2 递推公式是怎么推出来的斐波那契数的递推公式是题目给的不需要推导。但爬楼梯和最小花费爬楼梯的递推公式是你亲自推出来的这个推导过程就是动态规划的核心能力。先看爬楼梯。要到达第i阶最后一步只有两种情况从第i-1阶迈1阶上来或者从第i-2阶迈2阶上来。第一种情况包含的走法数正好等于到达第i-1阶的走法数第二种情况正好等于到达第i-2阶的走法数。这两种情况互不重叠所以总数相加得到dp[i] dp[i-1] dp[i-2]。再看最小花费爬楼梯。同样关注“最后一步从哪来”但这次不是计数而是选代价更小的方案。从第i-1阶过来要支付cost[i-1]从第i-2阶过来要支付cost[i-2]。两种方案的“前序代价”分别是dp[i-1]和dp[i-2]所以总代价是两种取min。这就是为什么公式里出现了min它就是最优化问题的标志。你会发现三题逛下来推导方法完全一致盯住最后一步枚举所有可能的前驱状态然后根据题目要求做加法或者取min。这个“最后一步分析法”后面刷所有一维DP都能用。2.3 初始化是重灾区先看斐波那契数。dp[0]0dp[1]1从i2开始递推。这个几乎没有争议空间因为数列定义就是这样。爬楼梯的初始化和斐波那契数有一点微妙的不一样。如果按“台阶数”来定义dp[1]1dp[2]2是最稳妥的写法然后从i3开始递推。这样做的好处是彻底避开dp[0]的语义之争。有些资料喜欢设dp[0]1从i2开始递推也能得到正确答案但对新手来说“走到第0阶有1种方法”这种说法实在太像人为硬凑出来的容易产生混乱。我的建议是用哪种都行但你要清楚自己在做什么不要在同一个代码里混用两套定义。最小花费爬楼梯的初始化是三道题里最坑的。题目明确说可以从下标0或下标1的台阶开始并且开始时不消耗体力。所以站在第0阶、站在第1阶时的最小花费都是0。注意这里不是cost[0]和cost[1]把cost算进去等于强迫自己必须从起点花钱完全违背题意。正确写法是dp[0]0、dp[1]0从i2开始递推。2.4 遍历顺序和返回值对应关系一维DP的遍历顺序大多数是从小到大也就是从下标2一路算到n。为什么不能从大到小因为dp[i]依赖dp[i-1]和dp[i-2]你只有先把前面的算出来后面的才有值可算。这个“由依赖关系决定遍历顺序”的原则放到二维DP、背包问题里也是一样适用的。返回值要和你定义的状态含义严格对应。斐波那契数返回dp[n]或滚动变量爬楼梯返回dp[n]最小花费爬楼梯如果采用“站在第i阶”的定义并且构造长度为n1的dp数组那么直接返回dp[n]。这个dp[n]对应的就是“越过最后一阶、真正到达楼顶”的状态。如果你用另一种定义返回的就是min(dp[n-1] cost[n-1], dp[n-2] cost[n-2])写起来啰嗦还容易漏。3. 实操实现与完整代码3.1 斐波那契数的四种解法第一种是暴力递归代码最短def fib(self, n: int) - int: if n 2: return n return self.fib(n - 1) self.fib(n - 2)这个解法在n大到一定程度时会非常慢因为大量重复的子问题被反复计算。画个递归树就能看到fib(5)要算fib(4)和fib(3)fib(4)又要算fib(3)和fib(2)同一个fib(3)被算了两次。n越大重复越严重时间复杂度是O(2^n)级别。第二种是记忆化递归用一个字典或数组存已经算过的结果def fib(self, n: int) - int: memo {0: 0, 1: 1} def helper(k): if k in memo: return memo[k] memo[k] helper(k - 1) helper(k - 2) return memo[k] return helper(n)第三种是标准dp数组版本def fib(self, n: int) - int: if n 2: return n dp [0] * (n 1) dp[1] 1 for i in range(2, n 1): dp[i] dp[i - 1] dp[i - 2] return dp[n]第四种是滚动数组版本也是面试里最常见的优化写法。既然当前值只依赖前两个值就没必要保存整个数组def fib(self, n: int) - int: if n 2: return n prev2, prev1 0, 1 for _ in range(2, n 1): cur prev1 prev2 prev2, prev1 prev1, cur return prev1这四种写法的递进关系其实就是动态规划最常见的优化路径暴力递归 → 记忆化 → dp数组 → 滚动数组。每一步解决一个问题重复计算、递归栈开销、额外空间。把这条路径走一遍你对空间复杂度的理解会直观很多。3.2 爬楼梯的收敛写法爬楼梯的递推公式和斐波那契数一样但基底不同。按台阶数定义dp[1]1、dp[2]2从3开始算def climbStairs(self, n: int) - int: if n 2: return n prev2, prev1 1, 2 for _ in range(3, n 1): cur prev1 prev2 prev2, prev1 prev1, cur return prev1注意这里和斐波那契数的一个小区别斐波那契数的边界是n2直接返回n而爬楼梯是n2直接返回n。原因很简单爬楼梯的第1阶只有1种走法第2阶有2种走法和斐波那契数列的0、1开头不一样。很多新手直接在爬楼梯里套用斐波那契的初始条件结果n2时返回1自然就错了。3.3 最小花费爬楼梯的两种状态定义先推荐我习惯用的一种dp长度设为n1dp[i]表示站在第i阶的最小花费初始dp[0]0、dp[1]0def minCostClimbingStairs(self, cost: List[int]) - int: n len(cost) dp [0] * (n 1) for i in range(2, n 1): dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]) return dp[n]这段代码里最容易被忽视的是循环范围range(2, n 1)。当cost长度为1时n1循环一次都不执行直接返回dp[1]0。这符合题意吗符合。因为数组只有一个台阶我可以直接站在下标0那个台阶上然后越过楼顶不需要花任何钱。很多人会在这里写错边界一看到n1就慌了实际上语义是对的。再看另一种写法dp[i]表示爬到第i个楼梯不是第i阶位置的最小花费。这种写法在最后一步会绕一点因为“爬到第i个楼梯”没法直接对应“越过终点”最终答案往往写成return min(dp[n - 1] cost[n - 1], dp[n - 2] cost[n - 2])也能通过但每次写都要多想一层更容易出bug。我强烈建议用第一种定义它把“楼顶”显式建模成dp[n]这个状态思维负担小很多。3.4 打印dp数组用实际数字验证逻辑以上面的cost [10, 15, 20]为例手动推导一遍dp数组的变化dp[0] 0站在第0阶还没开始花钱。dp[1] 0站在第1阶也没花钱。dp[2] min(dp[1] cost[1], dp[0] cost[0]) min(0 15, 0 10) 10从第0阶花10块钱爬上来更划算。dp[3] min(dp[2] cost[2], dp[1] cost[1]) min(10 20, 0 15) 15从第1阶直接跨到楼顶只花15。最终答案是15。注意这里有一条看起来反直觉的路径起始于第1阶直接跨两步越过第2阶到达楼顶。很多人拿着cost[10,15,20]心算时会以为答案是20或30因为他们默认每一步都得踩一个台阶。这就是dp数组的意义所在——它把所有合法方案都覆盖了包括“跳过一个台阶”的情况。我在实际调试时有个习惯不管题目多简单先把dp数组打印出来对着手动推导的值逐项核对。前几个值对上了后面基本不会再出问题。这个方法在刷更难DP题时更是救命稻草。4. 常见问题与排查技巧实录4.1 斐波那契递归超时重复子问题我在群里看到最常见的提交错误就是TLE而且几乎都发生在斐波那契数的暴力递归版本上。原因上面已经说过重复计算了太多子问题。leetcode的测试用例n能到30甚至更高暴力递归直接卡死。排查方法比较粗暴但很有效提交一次看看超时的n是多少然后在代码里统计某个函数被调用了几次。你会发现fib(3)在算fib(10)时被调用了十几遍。这不是递归本身的错而是没有记忆化。解决办法就是加缓存或者直接改成自底向上的迭代。记住这句话当你在递归里发现同一个参数被反复计算这个题八成应该用动态规划。4.2 dp[0]之争爬楼梯的初始化困惑爬楼梯的dp[0]到底等于多少是我见过讨论最多的问题。有的题解说dp[0]1代表“站在原地算一种走法”有的说dp[0]0然后从dp[1]1、dp[2]2开始。两种都能过但语义有差别。如果你不想陷入这种无意义的争论可以直接避开下标0。把dp[1]1、dp[2]2当作手工枚举的结果循环从3开始。这样既符合直觉也不会因为初始化错误影响后续。等以后刷到完全背包版本、把爬楼梯看成“用1和2凑n”的组合问题时你自然会理解dp[0]1在组合数学里的意义。现在这个阶段怎么顺怎么来别让初始化成为你刷题的心理障碍。4.3 最小花费的边界与越界最小花费爬楼梯的边界条件特别容易写崩我总结过几个高频错误cost为空或长度为1时没有进入循环直接返回初始值。对应代码里dp数组初始化长度要是n1否则访问dp[1]之类的就会越界。循环写成range(2, n)结果漏算了最后一个位置。这个问题在cost长度为2时特别隐蔽n2range(2, 2)是空的直接返回dp[2]但dp数组根本还没算到dp[2]。所以我强烈建议循环写成range(2, n 1)并且在写完后检查一下边界情况。初始化时把cost[0]和cost[1]写进去。这是逻辑错误不是越界但更难发现因为很多测试用例下结果只是偏大不一定报错。我自己第一次写746题就栽在这后来对着dp数组打印才发现起点被错误地计费了。4.4 滚动数组空间优化的坑爬到空间优化这一步常见的错误是更新顺序写反。比如下面这段prev2, prev1 0, 0 for i in range(2, n 1): cur min(prev1 cost[i - 1], prev2 cost[i - 2]) prev2 prev1 # 先更新prev2 prev1 cur # 再更新prev1这个顺序是对的。很多人会写成先更新prev1再更新prev2于是prev2拿到的是已经变成旧prev1的值整个递推链就断了。这个错误的隐蔽性在于小数据可能碰巧算对一旦n稍大结果就乱套。我的建议是空间优化版本一定要保留一个中间变量cur然后用“整体右移”的思维来更新两个游标不要试图在原变量上原地修改。给一个检查技巧优化完之后手动跑一两个小用例比如n3、n4把优化版和dp数组版的结果对比。对不上就说明更新顺序有问题。4.5 刷题习惯层面的一些心得最后聊一点方法论。这三道题我建议每个人都至少写两遍第一遍不看任何题解把自己卡住的点记下来第二遍对着代码随想录的思路重写重点检查自己之前忽略的细节。我在带训练营的时候发现很多同学刷DP容易陷入“背公式”的陷阱看到爬楼梯就写dp[i]dp[i-1]dp[i-2]看到最优化就写min。这样短时间确实能过几道题但一换场景就废。真正有用的做法是每次写代码前先在注释里写清三句话dp[i]代表什么、递推公式为什么成立、初始化依据是什么。写不出来就说明还没想明白这时候不要急着敲键盘。还有一个小技巧就是刻意练习“最后一步分析法”。拿到任何一道DP题先问自己如果我已经站在终点那么我的前一步可能来自哪里这个问题能帮你快速定位递推关系。我在做更难的一维DP题时仍然是靠这个朴素的方法打开思路三题入门练出来的这个反射比任何花哨的技巧都实用。