“更弱智的算法学习”这个系列写到第20天我自己都有点意外。前19天磕磕绊绊搞完了数组、链表、哈希、栈队列、递归、二分、双指针、排序还有简单的DFS和贪心入门。按大多数人的学习路径到这会儿可以硬着头皮上动态规划了但我在动手之前先说清楚今天这篇不是那种“状态转移方程拍脸上让你背”的文章我用的还是这个系列最擅长的“弱智学习法”——先把高深术语翻译成人话再用人话把代码写出来最后才回头对号入座去补术语。动态规划这四个字听起来像是什么高深的数学魔法但等你看完斐波那契和爬楼梯的推导过程你会发现它本质上就是“聪明的枚举”一个在你小学奥数或者日常点菜时就已经在用的小技巧。如果你是零基础、以前一看“动态规划”就头大或者哪怕你已经刷过几道题但始终是“看答案秒懂自己写就卡壳”这篇文章应该能帮你把这层窗户纸捅破。我们先不急着谈“最优子结构”“无后效性”这些吓人的名词我会用第20天这个节点上的思维进度把从暴力递归到动态规划的推导链路完整走一遍再拿两个经典问题现场演示。看完你会发现动态规划真不是什么高智商专属它就是一个有套路、能套模板、能一步步推出来的思考方法。1. 第20天的心态与准备前面19天到底练了什么这个系列叫“更弱智的算法学习”不是我自贬是真的在找一个更适合普通人的学习节奏。市面上很多资料默认你是科班、默认你数学底子好、默认你是天才然后一上来就扔给你状态转移方程。我怕的不是你看不懂怕的是你看完“哦原来如此”合上书自己动手时依然是零。所以前19天我做的所有事都是在给第20天铺路。我在第7天花了一整篇讲递归原因很简单动态规划的题没有递归基础根本讲不透。你可以这么理解动态规划就是从暴力递归里长出来的东西。如果你递归还没搞懂可以先回去翻翻之前那篇或者随便找一道递归题练练手但今天你至少要知道“函数调用自己”是怎么回事。到第19天为止我给自己梳理了一个简单的进度表你也可以照这个路线走阶段主题为什么必须学第1-5天数组、链表、栈、队列、哈希所有算法题的基本容器第6-8天递归、回溯理解“自己调用自己”和“状态回退”第9-12天二分查找、双指针、滑动窗口理解有序和局部性第13-15天排序、堆、优先队列理解顺序与贪心选择第16-17天贪心算法入门理解“每一步选当前最优”第18-19天DFS、BFS与图的基本遍历理解状态之间的跳转关系第20天动态规划入门把“搜索”从暴力变聪明你会发现我没有直接照搬大学算法课的顺序而是把一个普通人的学习路径重新排了一遍。贪心放在了DFS前面动态规划放在了DFS后面。这其实是有讲究的贪心让你理解什么是“局部最优”DFS让你理解什么是“状态的探索”有了这两个基础动态规划的“状态定义”和“状态转移”才不会像凭空冒出来一样。另外第20天这个节点还有一个心理因素。连续打卡20天最怕的不是不会而是“会的都做完了开始碰钉子”。动态规划天生就是劝退者它不像二分查找那样规则简单也不像BFS那样套路固定。如果你已经在这个位置恭喜你说明你已经啃下了前面所有基础模块具备研究动态规划的脑力带宽了。如果还没到这个位置也没关系看完今天的再回去补也不冲突。2. 动态规划不是玄学从暴力递归到记忆化搜索的完整推导链路很多教程讲动态规划上来就给你dp数组、状态定义、转移方程然后让你背。但我的实验结论是正常人根本背不住就算背住了也不会用。我自己第20天尝试了一个更笨但更能从根上理解的方法——先写暴力递归然后看它坐下了哪些重复劳动再把重复劳动的结果记下来最后把“记下来”这件事从递归里抽出来。第一步用斐波那契数列感受一下什么是暴力。斐波那契的数学定义大家基本都知道fib(0)0, fib(1)1, fib(n)fib(n-1)fib(n-2)。如果按定义直接写成递归代码长这样def fib(n: int) - int: if n 1: return n return fib(n - 1) fib(n - 2)这段代码本身没毛病简洁到不能再简洁。但如果你跑fib(40)会明显感觉卡顿。为什么我当初看别人的分析时只记住了“指数级复杂度”这个结论直到我自己画出调用树才真正理解。你算fib(6)的时候会发现它去求了fib(5)和fib(4)而fib(5)又会去求fib(4)和fib(3)。注意fib(4)算了不止一遍fib(3)算的遍数更多越往底层重复计算的次数越夸张。这就是“重叠子问题”它有个很生活化的解释你今天做米饭要打电话问妈妈放多少水明天做米饭又打电话问妈妈放多少水。你明明昨天已经问过了今天完全可以把这个答案记在冰箱贴上面。暴力递归就是“每次都重新打电话问”动态规划就是“第一次问了之后记下来之后直接看冰箱贴”。第二步我们用“冰箱贴”优化递归。这个“冰箱贴”在代码里叫备忘录一般用一个数组或字典实现def fib(n: int, memo: dict) - int: if n in memo: return memo[n] if n 1: return n memo[n] fib(n - 1, memo) fib(n - 2, memo) return memo[n]加了这三行代码同样的fib(6)每个子问题只计算一次复杂度从指数级降到O(n)。这个版本有个名字叫“记忆化搜索”或者“带备忘录的自顶向下递归”。这已经是动态规划的“近亲”了但还不是最终形态。第三步把“自顶向下递归”改写成“自底向上递推”。递归是从上往下问先问fib(6)要什么一层层往下拆。递推是反过来我先算最小的fib(0)和fib(1)然后推出fib(2)、fib(3)一步步推到fib(6)。改写成数组递推之后这就是教科书上说的“正宗动态规划”def fib(n: int) - int: if n 1: return n dp [0] * (n 1) dp[0], dp[1] 0, 1 for i in range(2, n 1): dp[i] dp[i - 1] dp[i - 2] return dp[n]很多人到这里就没下文了但是我建议你亲自把这三步各写一遍运行一遍看看耗时差距。等你真的感受到暴力递归怎么一步步变聪明你就会理解为什么动态规划不是玄学——它就是“把递归过程中重复计算的结果缓存起来并且改成从前往后推”。说到这里必须先做一个名词澄清。动态规划最常见的标签有两个“重叠子问题”和“最优子结构”。斐波那契完美演示了“重叠子问题”但它没有“选择”所以还不是完整意义上的动态规划。真正经典的动态规划题往往还有一个“选还是不选”的决策过程比如后面要讲的0-1背包。我建议你先把斐波那契这条推导链路彻底看懂因为它承载了“状态”“转移”“初始化”三个最基本概念的雏形。3. 这三个核心概念我用生活常识硬生生啃下来的很多教程讲到动态规划会直接甩出“状态”“状态转移方程”“边界条件”三件套搞得像黑话。第20天我决定换一种记法把这三个概念翻译成“我站在哪”“我能往哪走”“我一开始站哪”。先说“我站在哪”——状态。说白了就是dp数组的下标代表着什么含义。在斐波那契里dp[i]表示“斐波那契数列的第i项值”。在爬楼梯问题里dp[i]表示“爬到第i阶一共有多少种方法”。状态定义是整个动态规划最关键的一步定义得好转移方程顺手就来定义得烂后面寸步难行。我这个系列的原则是“状态必须能回答一个具体的问题”而不是模模糊糊地说“dp[i]是一个值”。怎么检验状态定义够不够清楚你闭上眼能把这个状态翻译成一句人话就算过关。再说“我能往哪走”——状态转移方程。它的本质是一个递推关系告诉你“当前状态是怎么由更小的状态算出来的”。我当初理解错的一点是总以为转移方程是从题目里“看出来”的其实不是它是从你的状态定义和问题要求里“推出来”的。以爬楼梯为例如果我知道“到第i-1阶的方法数”和“到第i-2阶的方法数”那么到第i阶就是最后一步从第i-1阶跨上来或者从第i-2阶跨上来两条路相加。转移方程不是灵感是逻辑推理的结果。最后说“我一开始站哪”——初始化和边界条件。初始化就是给dp数组最开头的那几个位置赋予一个明确值这个值通常不能由转移方程算出来必须靠常识和题目语义确定。很多人的困惑来了为什么斐波那契要特别设置dp[0]0、dp[1]1因为dp[0]和dp[1]没有“更小的前驱状态”公式dp[i]dp[i-1]dp[i-2]在 i0 或 i1 时是取不到合法参数的所以必须手动给值。我还踩过一个典型的坑硬背“dp[0]0”。后来做到另外一道题发现必须dp[0]1才正确因为那个dp[0]表示“空序列有1种组合方式”。所以不要背初始化要从意义上理解它。为了帮自己彻底理清我做了下面这个对照表概念学术叫法我的弱智翻译举例常见坑dp[i]的含义状态定义我站在哪爬到第i阶的方法数下标语义不清dp[i]怎么来转移方程我能往哪走dp[i]dp[i-1]dp[i-2]漏掉某一条转移路径dp[0], dp[1]的值初始化我一开始站哪dp[0]0, dp[1]1无脑设0导致语义错误我试图用这三问来帮助自己记忆。你以后做任何一道动态规划题先问自己我站在哪我能往哪走我一开始站哪这三问只要答得出来代码就是水到渠成的事情。答不出来的话说明你还没理解题目本身应该先回去画图、举例子而不是硬憋代码。另外这三问还有一个隐藏的第四问我按什么顺序走也就是遍历顺序。这个后续讲到0-1背包时才显得至关重要因为遍历顺序直接决定了结果的正确性。4. 爬楼梯从零开始推状态方程再顺手做一次滚动优化为了不让你觉得我光说不练现在找一个可以完整复活的入门题目。日常刷题社区里应该都见过这道题假设你正在爬楼梯每次只能迈1级或者2级台阶要爬上n级台阶一共有多少种不同的走法我第一次看到这道题时也是一头雾水想的是“这不就是用排列组合吗”。用动态规划来看它的逻辑比排列组合直观得多。先套用三问。状态定义dp[i]表示“爬到第i级台阶的不同走法数量”。转移方程要爬到第i级最后一步只有两种可能要么从第i-1级迈1级上来要么从第i-2级迈2级上来所以dp[i]dp[i-1]dp[i-2]。初始化第一级台阶只有一种走法直接迈1级所以dp[1]1第二级台阶可以11或直接2所以dp[2]2。从i3开始用循环递推答案就是dp[n]。写成代码大概是这样的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]这里有一个值得细想的细节为什么要从3开始循环因为dp[1]和dp[2]是我们手动初始化的。如果你非要写成从1开始也行但那样要么数组越界要么得在循环里加一堆防越界的判断代码明显变丑。养成好习惯手动初始化前面若干个必要状态然后从第一个“可以由转移方程推出”的下标开始循环。等你写完这个基础版本可能就会想需要一整个数组把所有中间结果都存下来吗答案是不需要。因为你推dp[i]的时候只用到了dp[i-1]和dp[i-2]更早的数据根本不会再被用到。这就像你走路的时候不需要记住自己三天前在哪个台阶只要知道上一级台阶和上上一级台阶就够了。这种把dp数组压缩成几个变量的技巧叫“滚动数组”或者“状态压缩”。压缩后的代码长这样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很多人看到这个写法会问prev, curr curr, prev curr这一行到底怎么执行在Python里右边的值会先用旧值计算完再统一赋值给左边。所以它等于temp curr curr prev curr prev temp我建议你初学阶段别直接用压缩写法先老老实实写一整个dp数组哪怕多占点空间也逼自己把dp[i]的语义想明白。等数组版彻底通了再压缩。压缩的好处不仅是省空间更能强迫你思考“哪些状态是真正需要保留的”这对后面理解背包问题的状态压缩很有帮助。爬楼梯这道题如果你已经会了还可以顺手试试它的两个变体检验一下自己是不是真理解了第一个变体是“每次可以走1级、2级或3级”问方法数第二个变体是“有的平台有体力花费需要算最小体力花费”。这两个变体不会改变整体思考方式但会逼你重新审视状态定义和转移方程。我只能说如果第一个变体你还想半天大概率是在生搬硬套原来的dp[i]dp[i-1]dp[i-2]而不是真正理解了“最后一步有哪些走法就把哪些子状态加进来”。5. 0-1背包为什么二维转一维时必须倒着遍历容量爬楼梯解决了一半的问题让你理解“状态怎么一层层推”。但动态规划里还有一些问题每一步都需要做“选择”纠结露骨。经典的0-1背包问题就是这种类型。问题长这样有一个能承重W的行李包有n件物品每件物品有自己的重量w[i]和价值v[i]问如何选取物品使包内总价值最大。每件物品要么装一下要么不装不能切割不能装一半所以叫0-1背包。我第一次看到这个问题第一反应是“按价值/重量比值排序从高到低装”。这个贪心思路听起来很有道理但实际上是错的因为物品不能分割把高价值高重量的物品装上可能导致包内剩余空间太小反而装不下几件轻但是性价比高的物品。贪心在局部看起来是对的但不能保证全局最优。动态规划就是用来做这种“组合决策”的。先定状态。这里有两个维度处理到第几件物品、当前用了多少容量。所以状态是二维的用dp[i][j]表示“在前i件物品中选且包内容量恰好为j或者说不超过j时能获得的最大总价值”。这个状态定义的合理性在于我们不可能只用一个一维下标同时表达“考虑了哪些物品”和“用了多少容量”这两个信息所以必须开二维数组。再推转移方程。对第i件物品做决策时只有两种可能。第一种不选它那dp[i][j]dp[i-1][j]意思是我只看前i-1件物品方案。第二种选它但前提是包容量足够即j w[i]这时dp[i][j]dp[i-1][j-w[i]]v[i]。注意j-w[i]是给这件物品腾出空间之后的剩余容量我们要用的是“在前i-1件物品里用j-w[i]容量能得到的最大价值”这体现了“之前的选择结果可以被引用”的动态规划核心思想。把两者取一个最大值就得到完整的转移方程dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i]) // 仅当 j w[i] 时初始化行和列容量为0时任何物品都放不下所以dp[i][0]0一件物品都不考虑时dp[0][j]0。代码大概长这样def knapsack_01(weights: list, values: list, capacity: int) - int: n len(weights) dp [[0] * (capacity 1) for _ in range(n 1)] for i in range(1, n 1): wt weights[i - 1] val values[i - 1] for j in range(1, capacity 1): if j wt: dp[i][j] max(dp[i - 1][j], dp[i - 1][j - wt] val) else: dp[i][j] dp[i - 1][j] return dp[n][capacity]注意一个小坑weights和values的下标我用了i - 1因为dp数组第0行表示“不考虑任何物品”物品编号从1开始对应到原始列表下标0。这是很多人写错的地方我再强调一次dp数组的行数比物品数多1列数比容量大1纯粹是为了让“前0件”“容量0”这些初始状态有地方放。二维版本虽然好懂但空间复杂度是O(n*capacity)在资源受限的情况下不够优雅。经典优化方法是把它压成一维数组dp[j]表示“容量为j时能装的最大价值”。代码改成def knapsack_01(weights: list, values: list, capacity: int) - int: dp [0] * (capacity 1) for wt, val in zip(weights, values): for j in range(capacity, wt - 1, -1): dp[j] max(dp[j], dp[j - wt] val) return dp[capacity]这里有个关键的、很多新手都会踩的坑一维优化后内层循环容量j必须从大到小遍历也就是从capacity往wt的方向遍历。为什么因为一维数组里只保留“当前层”的dp值而当我们更新dp[j]时需要用到dp[j-wt]的旧值这个旧值代表“只考虑前i-1件物品”时的结果。如果j从小到大遍历那么dp[j-wt]可能已经在当前这轮被更新过了覆盖成“已经考虑完第i件物品”的结果这样就会导致同一件物品被重复使用从而退化成完全背包问题而不是0-1背包。我打个比方你就能懂假设你面前只有一张白纸每一行只能写最新结果。你想用原来的第4行的数字去更新第6行但如果你先把第6行正着写了再回去找第4行发现它已经被你写成了一个新值。要避免这种串味只能从纸的下面往上写这样你用的永远是还没被动过的旧数据。这就是“倒序遍历”最直白的解释了。我在第20天做这道题时还特意做了一个小实验来验证自己没白学用二维版跑一遍答案再注释掉一维版对比两者输出是否一致。如果在容量够大的背包里塞几个数据你会发现结果一模一样但一维版省下了好几MB内存。这种动手对拍的习惯我强烈建议你养成它能帮你发现很多理解的盲区。6. 判断一道题能不能用动态规划两个信号和我的四问检查表你可能会问“爬楼梯和0-1背包都会了那我怎么知道一道新题该不该用动态规划”这个问题问得好在第20天这个节点我觉得比再刷十道题更有价值。动态规划不是万能药如果一道题用了暴力DFS也能轻松过你硬上动态规划属于过度设计。我的经验是新手先看两个信号重叠子问题和最优子结构。“重叠子问题”的信号是暴力递归时同样的参数组合会被重复计算。你可以在递归函数里加一个计数器看看某些参数出现了多少次。比如斐波那契的递归中n3这个子问题被反复计算了很多次这就是重叠子问题。没有重叠子问题动态规划的缓存就完全白搭因为每个子问题只算一次缓存没有任何复用机会。这种情况下通常直接搜索或分治就够了。“最优子结构”的信号是一个问题的最优解可以由子问题的最优解组合推导出来。这里最容易犯的毛病是把它跟“子问题都有最优解”混淆。所谓“最优子结构”强调的是我算出子问题的最优解之后可以直接拿来拼出父问题的最优解不需要回头再研究子问题的其他解。爬楼梯里全局方法数就是两个子方法数相加背包问题里装第i件物品的最优价值是“用剩余容量装前i-1件的最优价值”加本身价值。明显的反例是最短路径问题里如果图里存在负权边局部最短路径组合起来就不一定是全局最短路径这就破坏了最优子结构。如果这道题两个信号都出现了那就可以用我积累的四问检查表来落地状态怎么定义答出dp[i]或dp[i][j]代表什么并能翻译成一句人话。转移方程是什么当前状态由哪些更小的状态推出每一步有哪些选择初始化怎么定哪些状态不能由转移方程直接得到要靠常识赋值遍历顺序怎么走是从小到大还是从大到小是一层还是两层循环这个检查表看起来简单但实际做题时经常出问题。我见过很多新手也包括我自己初期在一道题上卡住不是不会写转移方程而是状态定错了。状态定成“以i结尾的最大子段和”和定成“前i个元素的最大子段和”整个思路完全不同。前者通常更容易和“当前位置必须选”绑定后者需要考虑“选或不选当前元素”两个分支。所以我把第一问放在最前面因为它几乎是成败的一半。为了更直观地展示四问的作用我列一个自查表题目类型状态示例转移关键初始化示例遍历顺序爬楼梯dp[i]爬到i阶的方法数最后一步来自i-1或i-2dp[1]1, dp[2]2从小到大0-1背包dp[i][j]前i件物品容量j最大价值选/不选第i件容量0或前0件都是0外层物品内层容量从大到小最大子段和dp[i]以i结尾的最大子段和dp[i]max(dp[i-1]a[i], a[i])dp[0]a[0]从小到大如果你能拿着这个表把每个经典题目都套一遍慢慢你会发现一种“题感”——看到“有多少种方案”“最大最小价值”“能不能达到某个目标”这类问题第一反应就是动态规划。当然也有例外有些“方案总数”题可以用组合数学有些“最值”题可以用贪心但那都是后话了从动态规划入手更稳妥不容易漏解。我在第20天给自己留的另一个小任务是拿之前做过的DFS回溯题来对比。比如走迷宫找路径和统计方案数走迷宫只需要找到任意一条路径DFS多半够了但统计方案数并且允许重复经过某些格子时经常就需要动态规划。这个认知算是今天最大的收获之一因为它把“搜索”和“动态规划”在我脑子里连成了一串。我个人在连续打卡20天之后最大的体会是算法学习从来不是比谁聪明而是比谁更能把大问题拆小。动态规划所有看似玄学的部分拆到最后都只是“别重复劳动把中间结果记下来”。第20天结束我不认为自己已经精通动态规划但我拿到了一个能自主推演的思考框架。如果你也想在这个系列里走到这儿我的建议很简单电脑前摊开草稿纸把今天提到的三道题——斐波那契、爬楼梯、0-1背包——全部从暴力递归开始推导一遍每一步都亲手写。等你写完你会发现自己已经跨过了那道“看答案秒懂、自己做就卡壳”的坎。