动态规划这块说实话是很多人的分水岭。有人觉得它玄乎有人觉得它就是“找规律”还有人刷了一堆题还是不会做新题。我自己前几年也被它折腾得不轻直到某天把几个经典问题真正“掰开揉碎”对比着看了一遍才有一种“原来是这么回事”的贯通感。这篇东西不是教科书式的定义罗列而是我基于一整套典型例题对比分析后沉淀下来的拆解方法、状态定义习惯和源码实现希望能帮你少走点弯路。1. 动态规划的本质不是“算法”是一套“记账”思维1.1 为什么叫“动态”规划先把“动态规划Dynamic Programming简称DP”这个吓人的名字拆开看。所谓“规划”本质是“在多个决策路径中选最优”所谓“动态”指的是这些决策是分阶段推进、后面的选择依赖前面结果的。大家初学时常说“DP就是记忆化搜索”这个理解方向是对的但不足以应付所有题目因为DP不光是“记忆”还有一套“怎么组织状态、怎么从小推到大”的章法。我更喜欢用一个生活化的类比讲DP假设你在爬一座台阶山目标是到山顶但你每到一个平台都能看到下一段路有几条分岔。DP的做法不是每次从起点重新试错而是每到一个平台就记下“我从起点到当前平台的最优开销/最优路径”。这样你越往上走手上的“记账本”越厚每次做决定只需参考最近几个平台的记录即可。这就是DP区别于暴力搜索的核心暴力搜索是重复计算同一批子问题DP是保证每个子问题只算一次并把结果存起来复用。1.2 三个先决条件最优子结构、重叠子问题、无后效性判断一道题能不能用DP不是靠感觉而是看三个条件是否满足。最优子结构大问题的最优解可以由子问题的最优解组合得到。比如背包问题里在容量一定时选物品的最优价值可以通过“少考虑一个物品、容量更小”的子问题推导。如果子问题的最优解不能支撑大问题最优解DP就失效了这一点必须牢记。重叠子问题不同的大问题会重复用到同一个子问题。举个最简单的例子斐波那契数列里F(5)和F(4)都会算F(3)暴力递归重复算了两遍。如果子问题完全不重叠那是分治法该干的活硬套DP反而浪费空间。无后效性马尔可夫性当前状态一旦确定它之前是怎么来的不再影响未来的决策。这也是初学最难理解的一点。说直白点状态就是一道分界线“过去的事翻篇了未来只看当前状态”。很多同学拿到题目总想先写转移方程我建议先回答三个问题大问题能否拆小拆出来的小问题有没有重复当前状态包含了全部历史影响没有三个都答“是”才进入下一步。1.3 状态、转移方程、初始化、遍历顺序DP四件套有了判断标准接下来就是解题“四件套”状态定义dp[i]到底表示什么是“前i个元素的最大值”还是“以i结尾的最优值”这是整个方程的灵魂定义错了方程全废转移方程状态之间怎么递推也就是“从哪些更小的状态算出当前状态”初始化最小状态值是什么边界条件处理对不对遍历顺序是从前往后、从后往前还是二维表格的特殊顺序这直接关系到状态依赖是否成立。这套思维框架其实不复杂难点在于每个环节都有“坑”。我后续的例题会挨个环节拆给你看尤其要把“为什么这样定义状态”讲透而不是直接甩一个方程。2. 典型例题横向拆解从一维到二维的跃迁这一部分是核心我会用五道难度递进的题带着你把四件套走一遍同时把“如何从一个题迁移到另一个题”的思路明确写出来。2.1 入门题斐波那契数列——先看懂“记忆化”到底记住了什么斐波那契数列对大多数人来说已经是“老熟人”但千万不要小看它它是我见过最好的入门样板因为它的所有要素都特别清晰。问题定义F(0)0F(1)1F(n)F(n-1)F(n-2)。状态定义dp[i] 斐波那契第i项的值。转移方程dp[i] dp[i-1] dp[i-2]。初始化dp[0]0dp[1]1。遍历顺序正向递增因为dp[i]依赖前面的小项。这是最朴素的写法。但我在实际面试里发现很多候选人止步于“写上dp数组循环”却说不清两层优化滚动数组降低空间复杂度、矩阵快速幂再提速。至少滚动数组必须会它体现的是“我只需要最近两个值”的观察力。def fib(n: int) - int: if n 2: return n prev2, prev1 0, 1 # 分别代表 dp[0], dp[1] for i in range(2, n 1): cur prev1 prev2 prev2, prev1 prev1, cur # 滚动更新 return prev1这段代码在LeetCode上能到O(n)时间和O(1)空间已经足够应对常规要求。我建议你在本地跑一遍并且手动用“记账本”的思路写下当i5时prev2、prev1的每一步变化很大概率能帮你打通“动态”的感觉。2.2 爬楼梯与最少硬币同一个框架两种决策方式斐波那契练手后马上看两道“变形”。它们都是“递推决策”模式但决策方式有差别。爬楼梯LeetCode 70每次可以走1阶或2阶问走到第n阶有多少种走法。它的方程是 dp[i] dp[i-1] dp[i-2]本质和斐波那契一模一样区别只在dp[0]1、dp[1]1这两个初始化的具体值。最少硬币LeetCode 322给定不同面额硬币coins和一个总金额amount求凑成总金额所需的最少硬币个数。它的状态定义是dp[i] 凑出金额i需要的最少硬币数。转移方程则要考虑所有可能的硬币面额def coinChange(coins, amount): dp [float(inf)] * (amount 1) dp[0] 0 for i in range(1, amount 1): for c in coins: if i c: dp[i] min(dp[i], dp[i - c] 1) return dp[amount] if dp[amount] ! float(inf) else -1两者的差异点值得细品爬楼梯是“加法性决策”把两种来源的走法数相加最少硬币是“最小值性决策”在多个候选面额里挑最优。很多新手会问“为什么有的dp用加法有的用min/max”答案在于你问的问题——“多少种方案”用加法“最优解”用最值。这个意识对后续做类型题至关重要。我个人的一个实操心得拿到这类题先想“dp[i]代表...”然后把“如何从dp[i-c]推导到dp[i]”写成一个句子最后再翻译成代码。写不出来句子就去掉干扰信息只留下“金额i和金额i-c的关系”这一件事。2.3 钢条切割与0-1背包首次面对“选与不选”的分支决策接下来难度上一个台阶你不再是从固定来源里递推而是面临“这个物品到底要不要选”的决策分支。这类题我称之为“决策型DP”最典型的两个模板就是钢条切割和0-1背包。钢条切割是《算法导论》里的经典有一根长度为n的钢条给定不同长度对应的价格price[i]求切割方案使得收益最高。状态dp[i]定义成“长度为i的钢条能获得的最大收益”。对于第一刀切出长度j剩下长度i-j可以继续切dp[i] max(price[j] dp[i-j])其中j从1到i遍历。这个方程的核心是“枚举第一刀怎么切”后面的过程被完全交给子问题dp[i-j]体现了最优子结构。0-1背包是另一个耳熟能详的经典有N件物品和一个容量为W的背包每件物品有重量weight[i]和价值value[i]每种物品只有一件求能装入的最大总价值。这里的状态必须升级成二维数组。设dp[i][j] 考虑前i件物品、背包容量为j时的最大价值。转移方程dp[i][j] max(dp[i-1][j], dp[i-1][j-weight[i]] value[i])这个方程式在“不拿第i件”和“拿第i件”之间取最大值。当写成Python时注意索引从1开始更方便初始化容量为0的行和列为0def knapsack_01(weights, values, W): n len(weights) dp [[0] * (W 1) for _ in range(n 1)] for i in range(1, n 1): w weights[i - 1] v values[i - 1] for j in range(1, W 1): if j w: dp[i][j] max(dp[i - 1][j], dp[i - 1][j - w] v) else: dp[i][j] dp[i - 1][j] return dp[n][W]钢条切割和0-1背包的相似性在于每个物品/每段长度有“取”和“不取”的决策。区别在于钢条切割的第一刀可以有无数种切法组合型背包是对每个物品做二元决策选择型。理解了这两者后面最长公共子序列之类就顺理成章了。真正需要小心的是二维DP的优化0-1背包可以用一维数组滚动压缩但遍历容量j必须从大到小否则一个物品会被重复使用。这是很多新手反复踩的坑。原因在于dp[j]更新时会覆盖旧值从大到小遍历保证使用的还是上一轮的“i-1”状态如果从小到大dp[j-w]已经被本轮更新过就变成了“完全背包”问题。def knapsack_01_optimized(weights, values, W): dp [0] * (W 1) for i in range(len(weights)): for j in range(W, weights[i] - 1, -1): dp[j] max(dp[j], dp[j - weights[i]] values[i]) return dp[W]这段代码建议自己敲三遍以上。第一遍照抄第二遍去掉注释默写第三遍边写边给同伴解释“为什么j要倒序”。能解释清楚才算真正会了0-1背包而不是背了模板。2.4 最长公共子序列LCS从“单串”到“双串”的思维升级再看一个经典给定字符串text1和text2求它们的最长公共子序列长度。注意子序列可以不连续只是保持相对顺序。这是从单序列DP到双序列DP的经典过渡。状态定义dp[i][j] text1前i个字符和text2前j个字符的最长公共子序列长度。转移方程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])这个方程的第一个分支好理解两个字符相等时一定可以从“去掉这两个字符的子问题”继承并延长1。第二个分支是初学者最容易懵的地方不想等时为什么取两边较小的子问题里的最大值其实它表示“至少有一边的当前字符不在公共子序列里”所以要么忽略text1的末尾字符要么忽略text2的末尾字符取两者的较大者。def longest_common_subsequence(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]我特别提醒一点LCS的状态维度是“两个序列各自的前缀长度”这跟单序列DP的“一维坐标”有本质区别。后来做编辑距离LeetCode 72时你会发现方程不过是LCS的变体插入、删除、替换三个操作分别对应三种来源。所以说LCS是一把钥匙一旦理解所有“双序列DP”的题目都能往这个框架里套。2.5 最长递增子序列LIS与编辑距离两种不同的“连续/不连续”套路最后再补两个有代表性的题目它们分别代表“尾部状态”和“操作状态”两种定义方式非常容易混淆。最长递增子序列LeetCode 300求数组中最长的严格递增子序列长度。常见做法是dp[i]定义为“以nums[i]结尾的最长递增子序列长度”转移时枚举i之前所有小于nums[i]的位置jdp[i] max(dp[i], dp[j]1)。这样做是O(n^2)但也可以用贪心二分patience sorting优化到O(n log n)。我建议你先把O(n^2)吃透因为它的状态定义方式能帮助你解决很多变种题比如“最长摆动子序列”、“俄罗斯套娃信封”。编辑距离LeetCode 72将word1转换成word2允许插入、删除、替换字符求最少操作次数。状态定义dp[i][j] word1前i个字符变成word2前j个字符的最少操作数。转移if word1[i-1] word2[j-1]: dp[i][j] dp[i-1][j-1] else: dp[i][j] 1 min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])其中dp[i-1][j]对应删除word1末尾字符dp[i][j-1]对应在word1后插入一个字符dp[i-1][j-1]对应替换末尾字符。这个转移的“三种操作路径”非常接近实际编辑行为熟悉它可以顺带秒杀“两个字符串的删除操作”LeetCode 583等同类题。我自己做LIS和编辑距离时有个习惯把每一行的dp值画出来观察数据在“表格”里的流动方向。LIS是一维的“回头找”编辑距离是二维的“左、上、左上”三方向流动。直观感受这个流动方向比背诵方程更有用。3. DP、贪心、回溯、分治别再傻傻分不清学DP到了一定阶段你一定经历过这种困惑有的题目用DFS回溯也能做有的用贪心就秒了为什么非要DP这里我根据个人经验整理一个“选型对照”的表格帮你快速定位一道题到底该用哪种思想。维度动态规划贪心算法回溯DFS分治法核心思想记子问题最优解避免重复每步选局部最优不回退枚举所有路径必要时剪枝拆成独立子问题再合并子问题重叠必须重叠通常不讨论可能重叠可加备忘录尽量不重叠最优解保证保证全局最优只对特定问题保证保证全局最优保证全局最优典型场景背包、LCS、编辑距离活动安排、哈夫曼编码、零钱兑换特定面额排列组合、走迷宫、N皇后归并排序、快速排序时间复杂度取决于状态数和状态转移代价通常O(n)或O(n log n)通常指数级通常O(n log n)这份表格有个很好用的判断流程先看是否有“重叠子问题”有重叠就多半是DP或备忘录DFS再看“局部最优能否推出全局最优”如果能贪心是追求效率的首选如果题目要求“找出所有方案”或“判断可行与否的某种组合”那多半是回溯。我举个例子帮大家理解贪心和DP的差异零钱兑换如果只有面额1、5、11求凑15的最少硬币数。贪心会先选11再选四个1得到5枚但最优其实是三个5也是3枚等等这里要给个更典型的例子才能体现差异。假设面额是1、5、11要凑15贪心是“能取大就取大”选11后剩4只能用四枚1总计5枚最优方案是三枚5总计3枚。这说明贪心只关注当前局部最优DP则把所有可能都算了。这个例子对我自己帮助巨大看代码前先用“局部最优能不能等于全局最优”检验能几行贪心搞定不能果断上DP。4. 实战中的坑与排查工具从“会做”到“能过”4.1 初始化与边界条件翻车高发区我见过太多人“方程写对了但代码跑不对”十有八九是初始化和边界条件的锅。这里总结几个高频事故点。第一dp数组维度与索引的错位。很多题目用dp[n1]是为了让dp[0]表示“空集/前0个元素”的状态但遍历时容易把下标搞混。比如0-1背包二维版本里weight数组和values数组的第0个元素对应的是i1的物品每次写weights[i-1]就啰嗦又容易错。建议统一在读取输入时把数组变成1-indexed或者在理解上把下标偏移量写进注释。第二初始化值到底填0还是无穷大。求最大值问题时非法状态填-1或负无穷求最小值问题时非法状态填正无穷。为什么因为min计算遇到非法状态如果填0会把不是正确答案的路径也算进去。比如最少硬币里dp[i]初始化为float(inf)才不会被“用不存在的面额组合”污染。我每次写完初始化都会问自己一句“这个值参与min/max运算会不会污染结果”这个检查百试百灵。第三二维DP表格的行列要不要多开一层。我的习惯是“多开一层再写方程”这样所有“前0个字符”和“容量0”都天然是0省去一堆if。缺点是内存占用稍高但绝大多数题目的规模完全无所谓代码清晰才是第一位。4.2 遍历顺序的逻辑推导遍历顺序是另一大高频坑。我总结一句话遍历顺序由状态依赖关系决定不是想怎么写就怎么写。一维递推、依赖前一项时从前往后0-1背包空间压缩时容量从大到小完全背包空间压缩时容量从小到大二维DP通常按行从小到大、列从小到大但如果方程依赖“左、上、左上”这个顺序刚好成立如果状态里有“回头依赖”可能得换顺序或者改状态定义。不要死记“0-1背包倒序、完全背包正序”要能现场推出来倒序是为了保证每个物品只用一次正序允许重复使用。有次我在评论区看到有人问“为什么我的完全背包答案偏大”几乎可以断定是循环顺序错了搞懂原理后这类问题一眼就能看出来。4.3 调试技巧把DP表格打出来看一眼这里分享一个我用了很久的调试方法打印dp表。不要只在脑子里凭空推演把中间状态print出来立即就能看到哪里不对劲。比如LCS问题你打了表之后会看到“相等字符”那一格的数值比左上角多1而不是比左边或上面多1这就验证了方程的分支正确。此外小规模手推永远比盲调快。做题时先用很小的输入n3或4手算一遍期望输出再让程序跑。如果差距不在最后一个格子而是一整行数值前移/后移那多半是索引偏移问题如果某一行数值突然全变那可能是初始化污染。4.4 常见问题速查表症状常见原因解决办法结果比答案大求max初始化时非法状态用了0比负无穷大把非法状态初始化为负无穷或-1并在转移时判断结果比答案小求min初始化用了0把非法状态当合法把非法状态初始化为正无穷01背包结果异常偏大j从小往大遍历物品被重复使用从大到小遍历容量j二维DP索引越界dp表没有多开一层或使用i-1时未判断统一用“前i个元素”的偏移定义LCS答案差1字符串下标对不齐text1[i-1]写成了text1[i]检查下标偏移这张表是我在刷题群答疑时反复用到的素材几乎覆盖了新人90%的报错来源。用之前列的问题对照自己的代码比一条条print调试要快得多。5. 避坑心得与学习路线建议5.1 三个特别值得注意的经验第一个经验状态定义宁可“笨”一点不要“巧”过头。我见过有人为了压一维把状态定义得特别抽象结果方程一写就错半天查不出bug。初期做题优先选择“最直观、最不容易出错”的状态定义等AC了再想优化。面试尤其如此先把正确解法写出来再提优化绝对比憋一个炫技但写错的方案强。第二个经验做题别贪多要把每个题吃透。我自己的节奏是同一道题写三遍第一遍不看答案硬想能想多久想多久第二遍对照题解修正状态定义和转移方程把“为什么我没想出来”写进注释第三遍隔一周再默写重点验证自己是否还记得“为什么这么定义”。这个方法看起来慢实际非常快因为它做的是一次次强化正确思维而不是无效刷题。第三个经验学会给题目“归类”。我在笔记本上把DP题分成几个板块线性DP爬楼梯、打家劫舍、区间DP石子合并、回文子串、背包DP0-1、完全、多重、树形DP树上最大独立集、状态压缩DP旅行商。每遇到新题先问他属于哪个板块再用对应模板往里套。这套分类法让我的“新题恐惧症”明显好转因为很多所谓新题不过是老模板换了层外衣。5.2 从“看懂源码”到“能写出来”的练习法很多读者拿了我文章里的Python代码看一眼觉得“懂了”关上页面就写不出来。这不是智力问题是缺少一个“复现训练”。我的建议是把本文所有源码都当作“参考答案”先合上文章用空白编辑器自己写一遍写完再对比看差异出在哪里。重点看以下几个位置循环变量到底是range(1, n1)还是range(n)dp表开多大、默认值是什么取数组元素时下标要不要减1。只要这三处每次都能写对说明你不是在背代码而是真的理解了状态和循环的对应关系。5.3 后续怎么扩展动态规划的边界非常宽本文没有展开的“树形DP”和“状压DP”是很多大厂面试的进阶考点。树形DP的核心是在树的递归过程中维护每个节点的状态比如“选或不选”典型的题有树上的最大独立集。状态压缩DP则把集合状态编码成二进制整数适合处理N在20以内的子集问题。学完本文的线性DP和背包DP后往这两个方向延伸路径会顺畅很多。如果时间有限我的建议是先吃透0-1背包和LCS这两道题的变体几乎覆盖了面试DP题目的半壁江山。剩下的再按需补齐就好。6. 动笔之前先回答这三个问题最后我想把整篇内容的“心法”压缩成三个问题。每次拿到DP题、看到别人讲解DP题都先问一遍自己这道题的“状态”到底是什么能不能用一个词说出来如“前i个物品的最大价值”当前状态是从哪几个方向转移过来的每个方向对应哪种决策初始化状态下哪些值是明确知道的哪些是非法/不可能到达的这三个问题想通哪怕方程第一遍写错你也能靠调试自己修正。怕就怕状态都没定义清楚就急着套模板那样翻车概率极高。这也是我个人从“畏惧DP”到“享受DP”的转折点。动态规划最迷人的地方在于它逼你把一个复杂问题拆成一条清晰的递推逻辑链。一旦建立起这种思维习惯你会发现很多看似无关的问题底层都共享同一套“记账本”思想。希望这篇细致的拆解也能帮你少走我当年走过的那些弯路。