打卡到Day40那天我真正感受到了什么叫算法训练营的分水岭。前一天的贪心算法题我还能靠局部最优推全局最优拍脑袋蒙对几道结果早上一打开题目列表看着斐波那契数这四字我还松了口气——这题多熟啊。然后鼠标往下滑爬楼梯不同路径我盯着第一道题半天没动手不是不会写递归而是隐约意识到代码随想录这一天的题要把我之前学过的几乎所有套路重新洗牌。这一篇就算是我自己的Day40复盘说说三道入门题怎么从暴力一步步走到动态规划以及DP五部曲到底该怎么用。如果你也正好在训练营中段摸爬滚打希望这份记录能给你一点参照。1. Day40的题目清单与训练营进度坐标先交代一下进度背景。Day40放在整个训练营里的位置挺特殊的数组、链表、哈希表、字符串、二叉树、回溯、贪心这些都过了一遍递归思维刚被二叉树和回溯题练得有点感觉贪心又让你开始习惯拍脑袋猜局部最优。就在你以为自己终于开始会做题的时候动态规划突然出现把一切都推到重来。我这里说的Day40对应的是动态规划基础篇当天题单大概是下面这几道题目核心考点我的第一反应509. 斐波那契数最基础的递推关系这还用DP递归秒了70. 爬楼梯发现隐藏的递推公式又是斐波那契746. 使用最小花费爬楼梯带开销的递推开始有点DP的味道了62. 不同路径二维DP与边界初始化排列组合好像也能算不同期次的训练营安排会有细微差异但入门题基本就是这个范围。很多人这一天会开始弃坑原因也很真实前39天你刚觉得二叉树不过如此回溯也就套模板结果拿到爬楼梯这道题连dp数组该是一维还是二维都要想半天。这种挫败感不是题目难而是你之前建立的解题直觉在DP这里不生效了。我自己的体会是Day40真正要解决的事有两件第一件理解重叠子问题和状态转移这两个词到底在说什么第二件把代码随想录反复提的DP五部曲落实到具体题目里而不是当成口号背过去。这两件事做不到后面01背包、完全背包、打家劫舍、股票问题全是空中楼阁。2. 贪心算法为什么在动态规划面前失灵了在聊DP之前必须先聊聊贪心。因为Day39和Day40之间那道看不见的裂缝就是贪心与DP的分歧点。贪心算法的核心思路是局部最优推导全局最优。做分发饼干那道题的时候你只需要每次把当前最小的饼干喂给当前胃口最小的孩子不需要回头看之前的选择。为什么不用回头看因为这道题的局部决策不会影响后面可用的选项也不存在这次选了A会让以后少一个机会的后悔场景。但爬楼梯这道题一出来情况就完全变了。题目问的不是怎么走最优而是一共有多少种走法。你站在第3级楼梯上既可能是从第2级跨了一步上来也可能是从第1级跨了两步上来。这两种走法都需要统计没有哪个比另一个更优——目标函数从求最优值变成了求方案总数。贪心算法在这种场景下直接没有用武之地因为根本没有一个局部最优可以贪。那递归行不行行但代价非常大。爬楼梯的朴素递归树会指数级膨胀n45的时候在你的电脑上已经能明显卡顿。问题出在重叠子问题上算f(10)要算f(9)和f(8)算f(9)又要把f(8)和f(7)重新算一遍f(8)被重复计算了两次f(7)被重复计算了三次——越往底层重复计算越离谱。动态规划做的事情说白了就是把这个重复计算干掉从最底层开始把每一个子问题的答案记下来后续需要的时候直接查表而不是重新递归。你可以把它理解成一个记账的过程。贪心是走一步看一步兜里揣一张当期最优的纸条动态规划是你有一本总账每一步都翻以前的账目算完当期再记一笔新的。这两个思维模式切换起来很别扭。我在Day39做题时习惯了先猜一个贪心策略然后跑两个用例验证到了Day40发现这招完全不灵了。后来才明白贪心和DP不是简单的前后关系而是一道分岔口当你发现一个问题的求解依赖多个更小的子问题并且这些子问题反复出现时你就该从贪心的路口拐进DP这条路了。3. 三道入门题从暴力到DP的完整演进这一章是当天的重头戏。我没有直接看题解而是把每道题都先从最原始的暴力写法开始推再一步步优化到DP。真的强烈建议你也这么走一遍直接背DP模板其实没意义。3.1 斐波那契数先写递归再懂DP为什么快斐波那契数这题谁都见过但训练营的难点在于逼你用动态规划的角度重新看它。题目本身一句话F(0)0F(1)1F(n)F(n-1)F(n-2)。大多数人的第一反应是写递归def fib(n): if n 1: return n return fib(n - 1) fib(n - 2)这代码干净、优雅但n40的时候就开始吃力n100基本算不出来。问题就出在那棵指数级膨胀的递归树上——你可以自己在纸上画一下n5的递归调用会发现fib(3)被算了两次fib(2)被算了三次。每个结点都在重复劳动复杂度是O(2^n)。第一个优化是加备忘录也就是记忆化搜索def fib(n): memo {} def helper(k): if k 1: return k if k in memo: return memo[k] memo[k] helper(k - 1) helper(k - 2) return memo[k] return helper(n)加了一个memo字典复杂度立刻降到O(n)。但这还不是标准的动态规划写法——它依然是从上往下递归只不过把重复计算结果缓存了。真正的DP思维是把这个过程反过来从底部开始填表def fib(n): if n 1: 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]你看递推公式本身没变变的只是遍历方向。自顶向下和自底向上是同一个关系式的两种展开方式但后者不需要递归栈也不会重复计算。这题还能做空间优化。你会发现dp[i]只用到了前两个值根本不需要整个数组def fib(n): if n 1: return n a, b 0, 1 for _ in range(2, n 1): a, b b, a b return b这就叫滚动数组。三种写法的复杂度对比如下写法时间复杂度空间复杂度朴素递归O(2^n)O(n)递归栈记忆化递归O(n)O(n)DP数组O(n)O(n)滚动数组O(n)O(1)这道题唯一的坑在于不要把n看成下标错位。n0时直接返回0dp[1]才是1很多人一上来先初始化dp[0]1结果整个数列整体平移一位最后全部报错。3.2 爬楼梯从题目里挖出递推公式爬楼梯这题是Day40真正的灵魂。题目看似比斐波那契难了一个档次但推到最后发现它就是披着应用题外衣的斐波那契。题目描述很简单你站在第1阶每次可以爬1阶或2阶问到n阶一共有多少种走法。关键是抓住最后一步。你要到第i阶只有两种可能从第i-1阶迈一步上来或者从第i-2阶迈两步上来。所以到第i阶的方案数就是这两种路径的方案数之和dp[i] dp[i - 1] dp[i - 2]这行式子一推出来后面的代码跟斐波那契一模一样def climbStairs(n): 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[2]2而不是3因为题目说每次可以爬1阶或2阶爬到第2阶只有两条路一次跨2阶或者连续跨两次1阶。有些人会手滑把它算成3多半是把爬3阶的走法提前脑补进来了。另一个经典争议是dp[0]到底该是几。如果你直接用dp[0]1来让公式统一确实方便但初学者很容易搞不清dp[0]代表什么。我更推荐直接初始化dp[1]和dp[2]绕开这个概念的坑。后面学到更复杂的题目时你再回来体会dp[0]的无意义但有价值。同样可以用滚动数组压缩空间def climbStairs(n): if n 2: return n prev, cur 1, 2 for _ in range(3, n 1): prev, cur cur, prev cur return cur我那天在这个滚动数组上踩了个小坑把prev和cur的赋值顺序写反了结果输出一直比正确答案小1。后来才反应过来这句赋值右边的prev是上一轮的cur必须同时更新不能拆成两个单独的赋值语句。3.3 不同路径一维数组的压缩技巧不同路径这道题把DP从一维拉到了二维是Day40真正拉开差距的一道题。题目说一个m行n列的网格机器人从左上角出发每次只能向右或向下走问到达右下角有多少条不同路径。一开始我想用排列组合直接算一共要向右走n-1步、向下走m-1步总步数mn-2在其中挑m-1个位置向下走答案就是C(mn-2, m-1)。这方法能算但训练营的用意显然不是考组合数学而是让你理解二维状态。DP的视角是这样的dp[i][j]表示从起点走到网格第i行第j列有多少条路径。由于机器人只能向右或向下那么到达(i,j)只能来自(i-1,j)或(i,j-1)所以dp[i][j] dp[i-1][j] dp[i][j-1]边界条件也很直观第一行的任意格子都只能一路向右走所以只有1条路第一列的任意格子只能一路向下也只有1条路。初始化时把这些格子都设为1def uniquePaths(m, n): dp [[1] * n for _ in range(m)] for i in range(1, m): for j in range(1, n): dp[i][j] dp[i - 1][j] dp[i][j - 1] return dp[m - 1][n - 1]注意Python里初始化二维数组要用[[1] * n for _ in range(m)]不要写[[1] * n] * m。后者会让每一行共享同一个列表对象改一行全部跟着变。二维DP的空间还能继续压。观察递推公式可以发现算第i行时只需要第i-1行和当前行的左边格子所以完全可以用一个长度为n的一维数组滚动def uniquePaths(m, n): dp [1] * n for i in range(1, m): for j in range(1, n): dp[j] dp[j] dp[j - 1] return dp[n - 1]这里最难理解的就是那句dp[j] dp[j] dp[j - 1]。第一次看到的人都会懵右边两个dp[j]到底谁是谁我的理解方式是这样的内层循环在更新第i行此时dp[j]还保留着上一行第j列的结果它代表dp[i-1][j]而dp[j-1]在本次循环里已经被更新成当前行第j-1列的结果了所以它是dp[i][j-1]。两者相加正好就是新的dp[i][j]。这行代码在纸上跑一遍比看十遍解释都管用。我建议你拿m3、n3手动推一轮第一轮循环结束后数组是[1,2,3]第二轮再走一遍就变成[1,3,6]最后的6就是答案。三种解法的效率对比解法时间复杂度空间复杂度组合数学O(min(m,n))O(1)二维DPO(mn)O(mn)一维滚动O(mn)O(n)做题时别急着追求一维滚动先二维想清楚再压缩。一维滚动是优化不是第一优先级。4. 被代码随想录反复强调的DP五部曲每一步都在解决什么Day40真正的收获不是AC了三道题而是把DP五部曲彻底内化了。代码随想录里反复强调这个套路我一开始觉得啰嗦直到自己独立做变体题时卡壳才服气。这五步是确定dp数组含义、确定递推公式、初始化dp数组、确定遍历顺序、举例推导dp数组。每走一步都有它存在的理由。第一步确定dp数组以及下标的含义。这一步最容易被跳过但恰恰是最关键的。比如爬楼梯dp[i]的含义是爬到第i阶的方法总数不同路径dp[i][j]的含义是到达第(i,j)格的路径数。含义不同后面所有推导都会跟着变。我见过有人把dp[i]理解成在第i阶还能走的步数最后公式怎么推都不对。这个错误不是计算问题是状态定义错了。第二步确定递推公式。递推公式不是背出来的是分析最后一步怎么来的推出来的。爬楼梯的最后一步要么跨1阶要么跨2阶不同路径的最后一步要么从上面来要么从左边来。这种最后一步分析是DP题最通用的思考方法。注意在推导公式时先不要想初始化很多人会把初始化和递推混在一起想结果越搞越乱。第三步dp数组如何初始化。初始化的依据是第一步里定义的含义。斐波那契里dp[0]0、dp[1]1是因为定义如此爬楼梯里dp[1]1、dp[2]2是由题目条件推出不同路径里第一行第一列为1是因为这些格子的路径只有一条。初始化的核心原则是给递推公式提供正确的起点而不是随便填。第四步确定遍历顺序。大多数入门题都是从前往后遍历因为dp[i]依赖更小的下标。但不同路径这种二维题你得保证计算dp[i][j]时dp[i-1][j]和dp[i][j-1]都已经算完。所以外层从上到下、内层从左到右。到了后面的背包问题遍历顺序会成为最大的考点但Day40你只需要建立这个意识遍历顺序取决于状态依赖的方向。第五步举例推导dp数组。这是我以前从来不做的一步也是Day40之后我改掉坏习惯的关键。拿n5跑一遍爬楼梯dp[1]1dp[2]2dp[3]3dp[4]5dp[5]8。如果结果是8说明逻辑没问题如果跑出别的数大概率是初始化或公式错了。手动推导的过程就像在给代码写冒烟测试。那天我做最小花费爬楼梯时就是靠第五步救命。题目要求从第0阶或第1阶开始每次爬1或2阶每个台阶有对应体力花费求到楼顶的最小花费。我一开始把dp[0]初始化为cost[0]导致结果偏小。后来手动推导dp数组才发现dp[i]应该表示到达第i阶并支付完该阶费用的最小花费从第0和第1阶开始时不支付任何费用所以dp[0]dp[1]0才对。这种错误不手动推两遍数组根本发现不了。初学者最常见的几个问题和修法我整理了一下错误类型典型表现修复思路状态含义模糊递推公式写出来了但解释不清dp[i]是啥回到第一步用一句话写清楚dp[i]初始化拍脑袋dp[0]乱设为1导致全盘偏置先问递推公式的最小下标需要什么起点遍历顺序混乱二维DP里用到了还没算出的值画依赖关系图从依赖方向反推遍历方向不举例验证AC一次就过换数字就错强制手动推导小样例再提交代码五部曲看起来很机械但它保证了你面对任何DP题都有一个稳定的处理顺序。尤其是Day40这种入门阶段靠着这个顺序你至少能写出一个结构正确的错误答案而不是坐在那里发呆。5. Day40之后的收尾动作错题整理与心态调整最后说说当天做完题之后我做了什么以及那些题解上不会写的东西。首先是错题整理。我给自己定了一条规矩每道DP题必须在本地按五部曲写一遍注释哪怕AC了也要写。格式很简单dp[i]代表什么、递推公式怎么来的、初始化为什么是这些值、遍历顺序为什么这样。写注释的过程能暴露很多自以为懂了的盲区。比如不同路径那道题我AC的时候用的是二维DP但写注释时发现自己根本说不清为什么边界是1这才老老实实回去补了滑动数组的推导。其次是节奏问题。Day40之后我明显感觉到一天刷三道新题 复习两道旧题已经是上限。DP和前面的章节不一样它需要你反复咀嚼。贪心题你AC了就是AC了DP题你AC了不代表你掌握了——换一个初始条件、改一个遍历方向你可能立刻又不会了。我在那天把做过的三道题换了各种变体去测爬楼梯改成可以爬1、2、3阶不同路径改成某几个格子有障碍每次改动都暴露出新的理解漏洞。心态方面我能给的唯一建议是怕做不出来很正常。我自己前39天建立了好像什么题都见过的虚假信心Day40被爬楼梯一道题就戳破了。但戳破是好事动态规划本来就是训练营中后期真正的分水岭你在这里卡住说明你在认真用脑而不是在背模板。一个非常有效的小技巧给自己留一个顿悟记录本。我第一次真正理解为什么斐波那契和爬楼梯是同一个递推时在旁边写了一句原来状态转移就是把最后一步的两种可能性相加。后来学到完全背包的时候回看这句话又冒出了新的理解。这种自己写下的顿悟比任何教程的干货都更适合你。Day40打卡结束那天我在便签上写了一句话动态规划不是一种解法而是一套记账的思维方式。后来学到01背包、完全背包我也一直用三步问自己这个状态的含义是什么、它从哪些状态转移过来、我先填哪里才不会用到还没算出的值。如果你今天正好卡在训练营的第40天别急着往下赶进度把斐波那契、爬楼梯、不同路径这三道题从头到尾推一遍再来一篇五部曲注释你回头看贪心题单的眼神都会不一样。