动态规划没那么难：从状态定义到转移方程的完整套路

1. 为什么我管动态规划叫“更弱智的算法”Day 58算法学到这里我发现自己越来越经常用“弱智”来夸一个解法。不是讽刺是真的觉得——原来这么简单的事我绕了那么大的弯才想明白。今天想复盘的是动态规划准确说是那些“一眼看上去高深莫测、想通了之后觉得不过如此”的动态规划题。如果你也在刷题或者学算法大概率听过这类话“动态规划嘛就是状态转移”、“关键是找到状态定义”、“不会DP就是不会面试”。然后你翻题解看到那些dp[i][j]、max(dp[i-1][j], dp[i][j-1]1)就头皮发麻。我懂我看了一个多月也是从那个状态过来的。先给这篇文章定个基调动态规划不是什么高冷玄学它本质上就是——“记住已经算过的结果别傻乎乎重复算”。就这么点事。我把它拆成三个步骤就是我在第58天彻底打通的那一刻总结出来的想清楚要记录什么状态定义想清楚怎么利用之前的记录推出新的记录状态转移想清楚最开始的记录怎么填初始化后面这5000多字全是围绕这三步展开的。每一步我都会贴出错题、翻车现场、还有我自己用着顺手的思考模板。你按这个节奏走真的能少走很多弯路。2. 动态规划到底在干什么——用斐波那契把这个事讲透2.1 递归版斐波那契为什么“蠢”先看所有教材都会写的例子斐波那契数列。def fib(n): if n 1: return n return fib(n-1) fib(n-2)这段代码逻辑没错但你跑fib(50)你的电脑风扇会告诉你答案——它要算到天荒地老。为什么因为同一个fib(40)会被拆出来算不知道多少遍。调用树是这个样子的为了算fib(50)先算fib(49)和fib(48)为了算fib(49)又要算fib(48)和fib(47)……你看fib(48)被算了两遍fib(47)被算了三遍。这种“同一个子问题反复求解”的情况术语叫重叠子问题。我试过给这段代码加一个计数器算fib(30)的时候fib(1)被调用了多少次答案是几十万次。就一个10以内的数字反复算了整个晚上——这种操作说它是“弱智级重复劳动”不为过吧2.2 记忆化给递归加上小本本优化思路特别朴素把算过的结果存起来下次再遇到直接用。memo {0: 0, 1: 1} def fib(n): if n not in memo: memo[n] fib(n-1) fib(n-2) return memo[n]这叫自顶向下的记忆化搜索。还是递归的形状但每个fib(k)只算一次。算到fib(50)飞快因为总共只需要算51个不同的值。这就是动态规划的雏形——不这就是动态规划本身。你注意所谓“动态规划”在斐波那契这里本质就是“你提前准备了一个本子边算边记”。2.3 自底向上连递归都省了记忆化搜索有个小缺点递归有调用栈深度限制Python里默认1000层搞不好就RecursionError。那干脆反过来从小的开始往上推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] dp[i-1] dp[i-2]这就是状态转移方程。dp[0] 0、dp[1] 1就是初始化。而dp[i]表示“斐波那契数列第 i 项的值”这就是状态定义。看到了吗动态规划三件套整整齐齐出现了。斐波那契简单到不值得单独学但它把DP的骨架暴露得一清二楚——你之后遇到的所有复杂DP无论二维三维、背包还是区间都在重复这个骨架。个人心得每次遇到一道新DP题我就先问自己三个问题——这个题要记录什么记录的东西怎么从前面的记录推出来最开头那个记录长什么样三个问题答完代码基本就写出来了。3. 状态定义怎么想——90%的人卡死在这一步3.1 状态定义错了后面全是白干很多人DP学不起来不是因为转移方程难推而是因为第一步“状态定义”就卡住了到底dp[i]表示什么为什么人家的题解写dp[i][j]是“前 i 个物品中选若干总容量为 j 的最大价值”这是怎么想出来的我的经验是状态定义不是凭空发明的它是由两个东西逼出来的题目问什么以及你当前能掌握什么信息。题目问“最长上升子序列的长度是多少”——那你自然需要一个东西表示“以某个位置结尾的最长上升子序列长度”于是dp[i] 以第 i 个元素结尾的最长上升子序列长度。题目问“从左上角到右下角有多少条不同路径”——你到达某个格子(i, j)的路径数量只跟到达它上面格子和左边格子的路径数量有关于是dp[i][j] 到达坐标 (i, j) 的路径数量。所以听我一句状态定义永远服务于你要的答案而且你要知道“当前这一步的答案”同时能由“之前几步的答案”推出来。想不出来的话常见套路很多其中最通用的是“以最后一步为锚点倒推”。3.2 倒推法从最后一步往回想我拿经典题“爬楼梯”来说。你一次可以爬1级或2级问爬到第 n 级有多少种方法。最后一步是什么要么是从第n-1级跨1级上来要么是从第n-2级跨2级上来。所以到达第 n 级的方法数 到达第n-1级的方法数 到达第n-2级的方法数。状态定义自然出来了dp[i]表示爬到第 i 级的方法数。转移方程就是dp[i] dp[i-1] dp[i-2]。初始化dp[0] 1在地面什么都不爬算一种、dp[1] 1。你再拿这个“最后一步”的思维去套后面我在5.3节写的背包问题会发现一个秘密所有递推关系本质上都在回答同一个问题——“我不走最后那一步会怎样”3.3 状态定义实战示范一维、二维怎么选我自己的判断标准是这样的如果答案只跟一个维度有关比如长度、容量、位置大概率一维DPdp[i]。如果答案要两个变量才能唯一确定比如两个字符串的各自长度、二维棋盘坐标那就是二维DPdp[i][j]。如果过程中你还需要区分“当前用了几个”或者“当前状态是A还是B”可能要加维度。别盲目追求“用最少的维度”——定义状态时宁可多一个维度把问题表述清楚也不要为了省空间把状态搞得语义不清。你写出来的代码是给人看、更是给你自己调试的语义清楚永远是第一位。优化维度那是后面“滚动数组”章节的事。4. 转移方程怎么推——从“我不会”到“有手就行”4.1 先列出来所有可能性都要覆盖到转移方程的推导核心就是一句话当前状态的所有可能来源全都列出来取最优/求和/计数。举个例子“不同路径”这道题。dp[i][j]表示从起点走到(i, j)的路径数。走到(i, j)有两种可能从上方的(i-1, j)走下来或者从左边的(i, j-1)走右来。没有第三种。所以dp[i][j] dp[i-1][j] dp[i][j-1]就这么简单。很多人一看到二维数组就慌了实际上你把“来源”列清楚公式就自己长出来了。4.2 转移方程里的陷阱漏掉来源、多加来源我在刷题时踩得最狠的坑就是来源没列全或者反过来列了不可能的来源。典型例子“跳跃游戏”系列或者带障碍物的路径题。如果你忽略了“当前位置是障碍物”这个条件直接把dp[i][j] dp[i-1][j] dp[i][j-1]套上去那障碍物格子的路径数量就变成了“能走”答案直接翻车。处理方式特别简单先把所有格子初始化成0然后遇到障碍物就跳过不更新它的dp值让它保持0。这一步我在4.4节会再次强调因为新版力扣的很多二维DP题都有这个坑。还有一个很容易犯的错边界上的来源。比如i0时dp[i-1][j]直接越界。所以所有二维DP都必须处理边界——要么给数组加一圈保护要么在循环里特判i0 and j0。4.3 用“表格法”手动推演小样例我调试DP题的固定流程是先拿一个很小的例子建一个表格手写填一遍。拿“不同路径”举例3行3列的网格dp[0][0]是起点。初始状态第一行1 1 1只能一直往右走每格都只有一种路径第一列1 1 1同理只能一直往下走然后从(1,1)开始填(1,1) (0,1) (1,0) 1 1 2(1,2) (0,2) (1,1) 1 2 3(2,1) (1,1) (2,0) 2 1 3(2,2) (1,2) (2,1) 3 3 6最后dp[2][2] 6答案是对的。手动填这个表的意义在于你能亲眼看到每一步数据的来源是什么而不是对着代码空想。遇到复杂题不要急着写代码先拿 3x3 这种小规模把表填出来填着填着你就知道转移方程对不对了。4.4 初始化时不注意这个细节100%翻车初始化最常见的坑是三个长度算错。一维数组开n还是n1。很多题是“前 i 个元素”的语义那就必须开n1让dp[0]表示“前0个元素”——空集的状态。边界初始化不完整。二维DP的第一行、第一列经常需要单独处理而不是循环里一下全算。比如“不同路径”第一行全是1如果你假装没有边界直接套公式第一行全变成0了结果全错。初始值语义混乱。dp[0]到底是“什么都没有的情况”还是“第一个元素的情况”你自己必须想明白并且写注释标出来。我见过太多人在这上面翻车表面上看是数组越界本质是状态定义和初始化对不上。规避方法很简单写代码前先写注释把dp[i]的含义用一句中文写清楚然后初始化那一行跟这个含义对一遍。比如注释写“dp[i]表示前i个物品的最大价值”那你初始化就是dp[0]0这是“前0个物品”合情合理。5. 经典题型完整实操最长公共子序列与0-1背包5.1 最长公共子序列LCS——二维DP的标准样板题面给定字符串text1和text2返回它们的最长公共子序列长度。比如text1 abcde、text2 ace公共子序列是ace长度3。注意子序列是不要求连续的所以在abcde里跳着取a、c、e。这题我第58天二刷的时候才真正掌握了状态定义的来源两个字符串一个指针i扫第一个串一个指针j扫第二个串到哪个位置能唯一确定我们当前考虑的范围答(i, j)。所以状态dp[i][j]表示text1的前 i 个字符与text2的前 j 个字符的最长公共子序列长度。转移方程的推导思路如果text1[i-1] text2[j-1]说明当前两个字符相等那它们可以拼到公共子序列的末尾所以dp[i][j] dp[i-1][j-1] 1。如果不相等那当前最长的公共子序列要么来自text1前 i-1 个和text2前 j 个的结果要么来自text1前 i 个和text2前 j-1 个的结果取最大dp[i][j] max(dp[i-1][j], dp[i][j-1])。代码写下来def longestCommonSubsequence(text1: str, text2: str) - int: m, n len(text1), len(text2) dp [[0] * (n 1) for _ in range(m 1)] for i in range(1, m 1): for j in range(1, n 1): if text1[i - 1] text2[j - 1]: dp[i][j] dp[i - 1][j - 1] 1 else: dp[i][j] max(dp[i - 1][j], dp[i][j - 1]) return dp[m][n]你看下标i-1和j-1这就是“前 i 个”和“第 i 个”的经典偏移。如果代码里总是出现dp[i-1]而不是dp[i]大概率是状态定义里用了“前i个”的语义。这个偏移统一处理好了面试手写这题会顺很多。我再提一个优化点LCS的dp[i][j]只依赖dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]也就是说当前行只依赖上一行和当前行。那就可以用两行数组滚动def longestCommonSubsequence(text1: str, text2: str) - int: m, n len(text1), len(text2) prev [0] * (n 1) cur [0] * (n 1) for i in range(1, m 1): for j in range(1, n 1): if text1[i - 1] text2[j - 1]: cur[j] prev[j - 1] 1 else: cur[j] max(prev[j], cur[j - 1]) prev, cur cur, prev return prev[n]空间从 O(mn) 降到 O(n)代码多两行但性能立刻上一个台阶。而且这里有个细节因为cur[j]更新时要用到cur[j-1]同一行左边所以内层必须从 1 到 n 正着遍历不能倒序。这个我和你强调一下后面背包问题正好相反。5.2 0-1背包——一维优化的“从后往前”之谜背包问题是另一个经典中的经典。题面有N件物品每件物品有重量w[i]和价值v[i]你有一个容量为C的背包问能装下的最大价值。二维版状态定义dp[i][j]表示“考虑前 i 件物品容量为 j 时能获得的最大价值”。转移方程推导——对第 i 件物品只有两种选择不装那么价值和“前 i-1 件、容量 j”一样dp[i][j] dp[i-1][j]装前提是j w[i]那么价值 dp[i-1][j-w[i]] v[i]。取两者最大值。写出来for i in range(1, N 1): for j in range(1, C 1): if j w[i]: dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i]) else: dp[i][j] dp[i-1][j]然后经典优化来了dp[i]这一行的更新只依赖dp[i-1]这一行于是可以把二维压成一维dp [0] * (C 1) for i in range(1, N 1): for j in range(C, w[i] - 1, -1): dp[j] max(dp[j], dp[j - w[i]] v[i])唯一需要注意的就是内层循环必须倒序。原因我在初学的时候完全想不通后来动手画图才意识到如果正序更新dp[j]当你更新到dp[j]时dp[j - w[i]]可能已经被当前 i 轮更新过了——那就变成了“同一件物品装多次”相当于完全背包而不是0-1背包。怎么让自己永远记住我习惯这样解释倒序遍历时dp[j - w[i]]还没被本轮更新还是上一轮的值——用旧值推新值天然保证每件物品最多取一次。你可以拿w1, v100、容量为3这种极端例子手推一遍正序和倒序的区别会看到正序结果直接多了好几个100那就是拿同一件物品反复装了。5.3 两个题放在一起才发现的共性第58天我最大的收获就是把LCS和0-1背包放在一起看。这两道看似毫不相干的题骨架一模一样都是二维状态都可以省成一维转移时都面对一个“取还是不取”的选择LCS里是“字符相等就取1不相等就取max”都踩同一个坑下标偏移。你能把这两题做透动态规划里最核心的思维就算建立起来了。后面什么编辑距离、最长回文子序列、子集和全都是这两题的变体。6. 常见翻车现场与排查技巧实录6.1 数组越界——不是不小心是状态定义没对齐我排过很多“IndexError”的错绝大多数都不是运气问题而是状态定义的下标语义出了偏差。比如我定义dp[i]是“前i个xx”但循环里写的是for i in range(len(nums))那dp[i]最多只能访问到dp[n-1]dp[n]就永远访问不到。反过来如果你定义的是“第i个xx”循环却从1开始填下标又错位一位。这类问题统一解法先写好注释定义再写循环循环的起点终点全部对照注释来一遍。6.2 初始化漏了一个状态整个结果崩掉举一个极小的栗子“打家劫舍”在每一家选择偷或不偷不能偷相邻两家。状态定义dp[i]表示前 i 家能偷的最大金额。转移方程dp[i] max(dp[i-1], dp[i-2] nums[i-1])。这题初始化要填dp[0] 0和dp[1] nums[0]。我当时只填了dp[0]第二个直接写进循环结果当n1的时候直接越界当n2的时候dp[2]就计算错了。解决办法很朴素凡是转移方程里有dp[i-2]的题目必须把前两个值都初始化好或者给数组多开两位兜底。我后来习惯把这类一维DP全部开n2长度前面多出来的位置留给边界省心不少。6.3 滚动数组用反了方向——0-1背包和完全背包的陷阱我在5.2节强调过0-1背包要倒序遍历。但如果你把j改成正序代码也能跑结果还“看似合理”——这正是最阴间的错误因为它不报错只有答案错。我自己的排查方法拿一组小数据手算一遍期望答案然后把正序和倒序的代码各跑一次对比dp数组。只要两次dp数组不同基本就是这里出了问题。这种手段在调试DP时特别常用打印DP数组永远比干瞪代码快得多。6.4 千万别急着一口气写完——先写小样例这里分享一个我用了很久的调试套路拿到题目先不管优化写最朴素版本可以先写记忆化递归再改递推。找一个极小的测试用例手动推出预期答案。把DP数组原样打印出来逐行对比。确认正确后再谈压缩空间、滚动数组这种事。很多同学有个坏习惯一上来就写最优解结果错了一头雾水。我第58天的经验是先跑对再跑快。算法学习阶段的正确性比性能重要得多。6.5 常见问题速查表现象可能原因排查方法数组越界状态定义“前i个”与循环写错位打印len(dp)和循环范围逐一对照注释答案边界不对缺少边界初始化检查dp[0]、dp[0][j]、dp[i][0]是否填对结果偏大一维背包正序遍历物品被重复取内层循环改为倒序结果偏小转移方程漏掉一种来源用3x3小样例手推填表对比代码超时递归无记忆化重复求解先改记忆化再考虑自底向上递推递归栈溢出自顶向下递归深度太大改自底向上迭代解决7. 心理建设与日常训练节奏——day58的真实体感算法学到第58天我想聊点代码之外的东西。如果你也在坚持刷题应该能体会那种“今天又没思路”的挫败感。但我要说一个反常识的观察遇到不会的题恰恰说明你在走上坡路。我以前想不通为什么有些题看了答案觉得“就这么简单”但自己想就是想不到。现在我明白了动态规划本质上是一种经验模式识别。你见过的状态定义越多你就能越快地从新题目里看出“这题跟背包很像”“这题跟LCS很像”。这不是天赋是积累。所以我每天的节奏是固定的先花15分钟尝试一道中等难度的DP题只允许自己想不查题解想不出来就花30分钟研究题解不背答案而是研究它的状态定义“为什么这么定义”有没有别的定义方式关掉题解自己重新写一遍完整代码写不出来就再看再写直到能独立完成复盘中把这道题归类贴上标签背包变种、区间DP、路径类、序列类。第58天的时候我大概刷了60多道DP题才开始能稳定地在中等难度题上独立写出状态定义。这中间没有捷径唯一的加速器就是总结归类。我一直到今天都保留一个文件夹专门记录每道题的“状态定义”和“为什么是这个定义”而不是记录整个题解。这个习惯比刷题数量管用得多。另外一个小技巧做DP题千万别跳过边界条件。很多题目你感觉是“主逻辑不会”实际上主逻辑都懂就是边界没处理好导致怎么跑怎么错。所以每次写完转移方程我都要问自己“i0、i1、j0、空串、单个元素”这些特殊场景会怎样养成这个习惯之后你的代码会稳定很多。最后再唠一句体会动态规划并不“弱智”——是我现在总算能用自己的话把它讲得像弱智一样简单。能把它讲“弱智”本身就是一种理解到位。58天前我看那些DP题解像看天书现在我能写出这样一篇长文给你复盘说明时间真的不会辜负每天半小时的重复练习。如果你也卡在某个算法点上别急着否定自己换个角度再推一遍说不定下一步就通了。