我见过太多这样的场景有人能把“最优子结构”“重叠子问题”“状态转移方程”这几个词背得滚瓜烂熟可拿到一道新题十分钟过去还是写不出第一行代码也有人刷了一大堆DP题经典模板都背下来了题目换个说法就彻底不认识了。动态规划在算法学习和工程优化里的位置非常特殊说它是“算法能力的试金石”一点不夸张——它考的不是记忆而是你把一个问题重新建模成子问题链的能力。这篇文章我想老老实实把动态规划从思考方式到解题步骤再到经典例题完整讲一遍。不堆抽象概念而是带着你从“敢写递归”一步步走到“空间优化后的递推代码”中间每一步为什么这么走、依赖关系怎么理、初始化要注意什么全都会说清楚。适合刚入门准备系统性刷题的同学也适合工作中需要处理路径规划、资源分配、序列比对等优化问题的开发者。文章里的代码以Python为主思路完全通用用其他语言对照着写也行。1. 三个底层概念先掰明白最优子结构、重叠子问题、状态定义1.1 最优子结构大问题为什么能拆开算动态规划能成立的第一个前提是最优子结构。用大白话说就是一个全局最优解它拆出来的每一段子问题的解也必须是那个子问题的最优解。想象一下你要从城市A开车到城市D中间必须经过B和C。如果有一条路线被证明是从A到D的最优路线那么从A到B这一段也一定是从A到B的所有路线里最优的那一条。为什么因为如果存在一条更短的A到B路线你只要把原路线里A到B这一段替换掉整条A到D路线就变得更短了——这就和“原路线已经最优”矛盾了。很多问题天然具备这个性质比如最短路径、编辑距离、背包问题也有很多问题不具备比如某些全局最优方案里的局部片段反而“走得偏”才能给后续腾出优势。这类问题用动态规划就会出问题更适合贪心或者搜索。所以拿到一道题第一件事不是急着写转移方程而是先问自己这个大问题能不能拆成几个独立的、可递推的小问题1.2 重叠子问题递归慢在哪记忆化救的是什么最优子结构说的是“能拆”重叠子问题说的是“拆了之后有大量重复计算”。这两个性质一起出现动态规划才值得用。以斐波那契数列为例。f(5) f(4) f(3)而f(4)自己又会去算f(3)、f(2)……如果把整个递归过程画成一棵树你会发现f(2)被算了三次f(3)被算了两次。n小的时候无所谓n到40左右普通递归已经要算上亿次n到100任何机器都跑不动。动态规划的应对思路极其朴素**算一次存一次下次直接查表。**这就是缓存也是后面所有DP实现的共同地基。很多人觉得“记忆化搜索”和“动态规划”是两个东西其实它们解决的是同一个问题——重叠子问题只是一个用递归加缓存的姿势一个用循环填表的姿势。1.3 状态定义先想清楚dp[i]到底存什么真正让初学者卡住的或者说让DP从“背模板”变成“需要理解”的地方是状态定义。dp[i]到底代表什么这是所有后续推导的地基。没有任何公式可以直接生成状态定义但它有很强的规律可循一维DP的状态绝大多数是“前i个元素怎么怎么样”或者“以第i个元素结尾怎么怎么样”二维DP的状态通常是“第一个序列的前i个与第二个序列的前j个怎么怎么样”背包类问题会在“前i件物品 容量j”这两个维度上做文章。状态定义定了转移方程基本是顺着语句抄一遍。我辅导过不少同学十个里有八个卡在状态定义这一步要么定义得太模糊导致转移方程怎么想都想不出来要么定义里掺入了决策比如“第i间必偷的最大值”导致后续处理变复杂。所以定义状态是DP里唯一需要“想”的部分后面全是流程化操作。2. 完整推导一次爬楼梯从暴力递归一步步变成递推数组2.1 敢写递归把“怎么走”翻译成“怎么调用自己”爬楼梯是最经典的入门题有n级台阶每次可以走1级或2级问一共有多少种不同的方式走到顶部。很多人觉得这题太简单不值得认真推导。但我想说这道题包含了DP从原形到最终形态的全部过程值得掰开揉碎看一遍。先别想DP只问自己一个问题**最后一步是怎么走的**答案只有两种——从第n-1级迈1级或者从第n-2级迈2级。那么到第n级的方式数天然等于“到第n-1级的方式数”加上“到第n-2级的方式数”。这句话翻译成代码就是暴力递归# 暴力递归直接把上面的逻辑翻译过来 def climb_recursive(n): if n 2: return n return climb_recursive(n - 1) climb_recursive(n - 2)这里的边界条件n 2也很直觉1级台阶只有1种走法2级台阶有“11”和“直接跨2级”两种走法所以返回n。很多人第一次看这段代码时会怀疑这是不是太简单了和动态规划有什么关系关系大得很。**递归写的是问题的定义递推数组写的只是执行顺序的优化。**你把这个定义写出来就已经完成了DP最难的一半。2.2 加缓存记忆化搜索就是DP的草稿暴力递归的毛病很明显重复计算。想想看climb_recursive(5)会调用climb_recursive(4)和climb_recursive(3)而climb_recursive(4)又会调用climb_recursive(3)和climb_recursive(2)。这个climb_recursive(3)就被算了两遍。n越大这种重复呈指数级增长。解决办法就是加一个缓存算过的值直接存下来下一次遇到同样的入参不再递归直接返回# 记忆化搜索用缓存干掉重叠子问题 memo {} def climb_memo(n): if n 2: return n if n in memo: return memo[n] memo[n] climb_memo(n - 1) climb_memo(n - 2) return memo[n]加了这一层缓存之后每个n只需要被真正计算一次递归树被剪成一条链时间复杂度从指数级降到了线性级。到这一步“重叠子问题”这个抽象概念已经变成了一行具体的代码——这就是动态规划的草稿版自上而下思考自下而上填充。2.3 换数组递推顺序背后的依赖关系记忆化搜索虽然能运行但有两个小问题一是递归调用有函数栈开销n特别大时可能爆栈二是“自上而下”的调用顺序让你很难直观看到状态之间的依赖关系。于是我们把递归翻成循环形式的递推填表# 动态规划自下而上填表 def climb_dp(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]注意这里的遍历顺序从3到n正着填。为什么因为dp[i]依赖的是dp[i-1]和dp[i-2]这两个状态必须已经在dp[i]被计算之前算出来。依赖方向决定了遍历顺序这是DP里一条永远成立的规律。最后你还会发现整个dp数组在计算过程中只用到前两个值后面的值用过就再也用不到了。于是数组都没必要开满用两个变量滚动就够了# 空间优化滚动变量 def climb_opt(n): if n 2: return n a, b 1, 2 for _ in range(3, n 1): a, b b, a b return b爬楼梯这一题从暴力递归到记忆化到递推数组再到滚动变量每一步都有明确动机没有一步是为了炫技。你能亲手走一遍这个过程后面遇到再复杂的DP思考路径也都是这一条的延长线。3. 解题五步法用“打家劫舍”把这套流程走一遍3.1 定状态dp[i]的含义直接决定后续所有代码“打家劫舍”是另一个非常经典的一维DP一排房子每间房子里有一定金额不能偷相邻的两间问最多能偷到多少钱。这道题比爬楼梯稍微进了一步因为它的转移方程不是直接“加法”而是带决策的“取最大值”。按五步流程走第一步永远是定状态。这里我用“前i个房子”这个口径dp[i] 考虑前i个房子也就是索引0到i-1时能偷到的最大金额。为什么用“前i个”而不是“第i个”因为用“前i个”配合长度为n1的数组空房子0个就有一个明确的占位初始化和边界判断都会顺手很多。这一点后面还会展开讲。3.2 写转移方程这一步需要的是“可能性枚举”状态定义定了转移方程就是枚举当前房子的所有可能不偷第i个房子那最大金额就是dp[i-1]偷第i个房子那相邻的第i-1个房子不能再偷所以最大金额是dp[i-2] nums[i-1]。两者取最大值dp[i] max(dp[i-1], dp[i-2] nums[i-1])我第一次写这道题时总觉得应该写dp[i-1] nums[i]之类的变体但顺着“偷/不偷”两个分支想思路就特别清晰。转移方程本质上是把所有到达当前状态的可能性列出来再按题目要求取max、取min或者求和。很多初学者卡在转移其实是没把“当前状态有哪些前驱状态”枚举完整。代码实现def rob(nums): n len(nums) if n 0: return 0 if n 1: return nums[0] dp [0] * (n 1) dp[0] 0 # 没有房子收益为0 dp[1] nums[0] # 只有一间房子那就偷它 for i in range(2, n 1): dp[i] max(dp[i - 1], dp[i - 2] nums[i - 1]) return dp[n]3.3 初始化与遍历顺序最容易丢分的地方初始化本质上是把“最小的子问题”手算清楚。在打家劫舍里最小的子问题是dp[0]和dp[1]0间房收益当然是01间房收益就是这间房的金额。这两个值定了后面的递推才有起点。遍历顺序同样由依赖关系决定dp[i]依赖dp[i-1]和dp[i-2]所以从2到n正着遍历。这里没有什么需要“猜”的看你依赖谁就知道谁得先算完。常见错误是把dp[2]提前初始化成一个“看起来合理”的数值导致后续全部偏移。我的习惯是先写转移方程再把递归的边界条件翻译成初始化的具体值不要凭感觉加额外初始化。3.4 空间压缩有些时候只用两个变量就够了转移方程里dp[i]只依赖dp[i-1]和dp[i-2]和爬楼梯的情况一模一样完全可以用两个滚动变量替代整个数组# 空间优化到O(1) def rob_opt(nums): prev2, prev1 0, 0 for x in nums: prev2, prev1 prev1, max(prev1, prev2 x) return prev1这里prev2对应dp[i-2]prev1对应dp[i-1]每处理一个新房子就滚动一次。很多人在面试里被问到“能不能优化空间”指的就是这一步。以后遇到任何“dp[i]只依赖前面固定几个值”的转移都可以照这个方法压缩。4. 0-1背包二维DP的经典模型与一维空间压缩4.1 背包问题的状态有两维选到第几个、还剩多少容量如果说前面几道题是一维DP的地基那0-1背包就是把维度撑到二维的分水岭。题目是这样有n件物品每件有自己的重量w[i]和价值v[i]背包能承受的最大重量是W每件物品只能选择“拿”或“不拿”问能装进背包的最大总价值是多少。为什么这个问题不能用一个一维的dp[i]解决因为“考虑前i件”这个信息里没有承载“重量限制”这个维度。同样的前i件物品在不同剩余容量下能获得的最大价值是不同的。所以状态必须同时记录两个信息dp[i][j] 从前i件物品中选择总重量不超过j时能获得的最大价值。这就是二维DP的标准定义方式。第一维管“物品编号”第二维管“容量”两个维度互相约束。4.2 二维表怎么填用一组具体数据把过程走一遍有了状态定义转移方程顺理成章。处理第i件物品时只有两个选择不拿第i件价值保持为dp[i-1][j]拿第i件前提是当前容量j大于等于w[i-1]价值为dp[i-1][j-w[i-1]] v[i-1]。两者取最大值dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i-1]] v[i-1])为了不空谈我找一组具体数据手算一遍。假设3件物品如下物品编号重量价值124212333背包容量为4。初始时dp[0][j]这一行全是0因为一件物品都不选价值当然是0。接下来逐行填表容量j01234只考虑第1件00444考虑前2件02466考虑前3件02466看第三行容量为3时可以同时拿第1件重2、值4和第2件重1、值2总重量正好3总价值6。第三件重量3、价值3容量3时拿它只值3不如6。容量4时拿第1、2件已经是6第3件拿不拿都无法超过所以答案就是6。这种手工填表的过程比背十遍转移方程都有用。先用小样例把表格走一遍你才能真正知道每个格子是怎么来的。代码实现def knapsack_2d(weights, values, capacity): n len(weights) dp [[0] * (capacity 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(capacity 1): if j weights[i - 1]: dp[i][j] dp[i - 1][j] # 放不下只能不拿 else: dp[i][j] max( dp[i - 1][j], # 不拿 dp[i - 1][j - weights[i - 1]] values[i - 1] # 拿 ) return dp[n][capacity]4.3 一维数组改造为什么容量必须倒着遍历二维版本的空间复杂度是O(n*W)物品多或容量大时内存扛不住。观察转移方程你会发现dp[i][...]这一行只依赖dp[i-1][...]那一行再往前的行完全用不到。所以我们可以只保留一行把二维数组压成一维def knapsack_1d(weights, values, capacity): dp [0] * (capacity 1) for i in range(len(weights)): for j in range(capacity, weights[i] - 1, -1): dp[j] max(dp[j], dp[j - weights[i]] values[i]) return dp[capacity]注意内层循环的j是倒着遍历的这是0-1背包一维化里最关键、也是最容易被忽略的细节。为什么必须倒着想象一下如果你让j正着从0到capacity遍历当你在更新dp[j]时dp[j - weights[i]]可能已经在同一次外层循环里被更新过了。也就是说这个值已经包含了“当前这件物品”的贡献。你再拿它加values[i]相当于同一件物品被拿了多遍。正序更新得到的是完全背包每件物品可以无限拿倒序更新才能保证每件物品最多拿一次。之所以倒序安全是因为dp[j - weights[i]]在倒序时还没被本轮更新它仍然保存着上一轮也就是没拿当前物品时的值。这一点理解了你就再也不会搞反0-1背包和完全背包的遍历顺序。4.4 常见变体恰好装满、方案计数、最少个数背包题在算法题里能变出很多花样但都是在这套转移方程上做文章恰好装满如果题目要求“正好把容量W装满”初始化就不能全部给0而是dp[0]0其余dp[j]负无穷或者一个足够小的数。原因是“恰好装满”意味着每个状态都必须由真实可选的组合拼出来不存在的东西不能默认0。求方案总数把转移方程里的max改成求和。dp[j] dp[j] dp[j - weights[i]]含义是“达到容量j的方案数等于不用当前物品的方案数加上用当前物品的方案数”。求最少物品个数或最小价值把max改成min同时初始化正无穷。这类题刷起来特别多但搞清楚母题后变体只是改一两个字母。5. 编辑距离和最长公共子序列二维DP的表格套路5.1 最长公共子序列相等和不相等两种情况的处理最长公共子序列LCS是面试里出现频率极高的题给定两个字符串s1和s2找出它们最长的公共子序列长度。注意子序列不要求连续只要保持相对顺序。这道题看到“两个字符串”直接反应是二维DP。定义状态dp[i][j] s1的前i个字符与s2的前j个字符的最长公共子序列长度转移分两种情况如果s1[i-1] s2[j-1]说明当前字符可以匹配上长度在dp[i-1][j-1]的基础上加1如果不相等那这两个字符至少有一个不在最终公共子序列里所以取“去掉s1的第i个字符”和“去掉s2的第j个字符”这两种情况的最大值。def lcs(s1, s2): m, n len(s1), len(s2) dp [[0] * (n 1) for _ in range(m 1)] for i in range(1, m 1): for j in range(1, n 1): if s1[i - 1] s2[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]这里dp数组特意做成(m1)*(n1)目的就是给“空串”留位置。第一行和第一列初始化全0表示空串和任何字符串的公共子序列长度都是0。5.2 编辑距离把删除、插入、替换写成转移方程编辑距离和LCS是“一类题”的两个方向。编辑距离问题描述是允许对字符串做三种操作——插入一个字符、删除一个字符、替换一个字符每种操作代价都是1问把s1变成s2最少需要多少次操作。状态定义几乎一模一样dp[i][j] 把s1的前i个字符变成s2的前j个字符所需的最少操作数初始化是这题的一个考点dp[i][0] i意味着把s1的前i个字符全部删掉才能变成空串dp[0][j] j意味着从空串插入j个字符才能变成s2的前j个。转移方程同样分两种s1[i-1] s2[j-1]当前字符不用动直接继承dp[i-1][j-1]不相等就需要从三种操作里选代价最小的删除dp[i-1][j] 1删掉s1的当前字符插入dp[i][j-1] 1在s1中插入一个和s2[j-1]相同的字符替换dp[i-1][j-1] 1把s1[i-1]直接换成s2[j-1]。def edit_distance(s1, s2): m, n len(s1), len(s2) dp [[0] * (n 1) for _ in range(m 1)] for i in range(m 1): dp[i][0] i for j in range(n 1): dp[0][j] j for i in range(1, m 1): for j in range(1, n 1): if s1[i - 1] s2[j - 1]: dp[i][j] dp[i - 1][j - 1] else: dp[i][j] min( dp[i - 1][j] 1, # 删除 dp[i][j - 1] 1, # 插入 dp[i - 1][j - 1] 1 # 替换 ) return dp[m][n]这里有个很妙的对称性插入和删除本质上是一个操作从两个方向看。站在s1的角度是删除站在s2的角度就是插入所以转移方程里这两个方向都出现min取最小即可。5.3 从dp表反推答案追着转移方向走回去很多场景不光要长度/距离还要具体方案。比如文本对比工具除了告诉你两段文本差多少还要把差异标出来。这时就需要从dp表反推。以LCS为例从dp[m][n]开始往回走如果s1[i-1] s2[j-1]且dp[i][j] dp[i-1][j-1] 1说明这个字符确实被选进公共子序列了记下它然后斜着走到(i-1, j-1)否则比较dp[i-1][j]和dp[i][j-1]哪个大就往哪个方向走如果相等任选一个方向这对应多个不同子序列的情况。反推的代码并不复杂但它要求你保留完整的二维表。这也引出了一个重要提示如果题目要求输出方案空间压缩就要三思因为滚动数组会把中间状态丢掉。5.4 二维DP通用套路先画表再找依赖方向LCS和编辑距离看多了你会发现这类“两个序列”的二维DP有非常固定的套路字符串匹配、序列比对、相似度计算这类关键词出现时第一反应就是二维DP状态定义总是“dp[i][j] 第一个序列前i个与第二个序列前j个的某个指标”转移方程就是在“当前两个字符相等/不相等”两个分支下分别讨论从哪个方向转移而来就决定了表格的填充顺序。我自己的习惯是在草稿纸上先画一张小表手算几格再写代码。空想状态转移很容易绕晕但表格画出来依赖方向一目了然。这比任何口诀都管用。6. 刷DP题最常翻车的三件事初始化、遍历顺序与滚动数组6.1 下标差一数组长度n1到底好在哪DP代码里最常见的bug是“差一错误”。我见过太多人写循环时用错了下标或者取元素时多取了少取了一个。用n1长度的数组核心好处是给“空状态”一个位置。字符串题目里的空串、背包题里的0件物品、打家劫舍里的0间房子全部落在dp[0]这个位置上。代价是你在取原始数据时要记得做一次偏移比如物品重量是weights[i-1]房子金额是nums[i-1]而不是weights[i]。如果你用的是“以第i个元素结尾”这种状态定义数组长度可以正好是n取元素也不需要偏移。两种口径都正确但绝不能在一道题里混用。A同学有一次debug到怀疑人生最后发现就是某个循环里看的是nums[i]另一个循环里写的是nums[i-1]状态定义的口径完全对不上。写代码前先确认口径dp的下标到底是“数量”还是“索引”。6.2 遍历顺序什么时候正序、什么时候倒序、能不能换遍历顺序是DP里最容易“背错”的部分尤其是背包。我的建议是不要背结论而是从依赖关系现场推如果当前状态依赖的“前驱状态”来自上一轮计算上一件物品、上一个字符那这一轮更新时就不能提前覆盖它们背包倒序遍历的原因就在这里如果当前状态依赖的是本轮已经算出的更小状态那就要看题目允许不允许这种“重复使用”。完全背包允许重复拿物品所以正序0-1背包不允许所以倒序对于LCS、编辑距离这种二维表格由于每个格子依赖的是左边、上边和左上角只要两层循环方向都是从左到右、从上到下就不会出问题。还有一个我自己的经验不确定时就把二维表的过程在脑子里走一遍。比如0-1背包容量倒序的本质是“锁住上一行的值”你理解了这一点就再也不会把两个版本的代码弄混。6.3 滚动数组的代价想在最后反推方案时会吃亏前文反复提到滚动数组能把空间从O(n)降到O(1)但它不是免费的。滚动数组只保留“最近几行”的值一旦题目要求输出具体方案——比如选了哪几件物品、最长公共子序列到底是什么、编辑距离的每一步操作是什么——纯滚动数组的信息就不够了。这时候有几种做法保留完整的二维表空间换方案这是最直接的做法额外开一个决策数组在每步转移时记录“是从哪个方向来的”最后靠这个数组反推部分问题还可以在最后做一次“暴力反推”但前提是你保留了足够定位的状态信息。所以我在做题时的习惯是**先按完整二维表把思路捋清楚并保证正确再考虑要不要滚动数组优化。**优化是加分项但不是所有题目都该做。6.4 别对每道题都用DP先判断有没有最优子结构最后想泼一盆冷静水动态规划不是万能的也不是每道优化题都必须用DP。判断一道题适不适合DP就看两个性质有没有最优子结构有没有重叠子问题。前者保证了“能拆”后者决定了“拆了值得”。举个反例假设有面额为1、5、11的硬币要凑出15元。贪心策略是每次取最大面额先拿11剩下4元用4个1元补齐一共需要5枚硬币。但最优解其实是3个5元硬币只要3枚。这道题贪心会翻车因为它不具备“贪心选择性”而DP恰好能处理这种需要全局权衡的场景。反过来比如活动安排这种“选完之后不影响后面选择”的问题贪心又快又对你用DP反而绕远。我的判断流程是先试着把问题写成递归定义看看能不能自然拆出子问题如果能拆再看拆出来的子问题是否会被反复计算。两个条件都满足再进入状态定义的环节。如果缺了其中任何一个就该考虑换思路了。学动态规划我认为最值得养成的习惯不是刷题量而是先写递归、再画表格、最后写递推这个“三步走路”。这个顺序看着绕但它能确保每一步的动机清楚不会出现“代码能跑但说不清为什么”的黑箱状态。动态规划与其说是一个算法不如说是一种把思考显式化的习惯。状态定义清楚、依赖关系理顺、边界条件填对剩下的事情其实都是水到渠成。用到后来你会发现真正难的从来不是写代码而是肯不肯静下心先把问题重新定义一遍。