我最早学动态规划的时候最大的感受是所有教程都在抛“状态转移方程”但没人告诉我这个方程是怎么被想出来的。后来把找零钱、最大连续子序列和、最长上升子序列、最长公共子序列、最长公共子串、0-1背包这六个经典问题放在一起反复对比才慢慢摸到门路动态规划不是靠灵感而是一套有固定拆解方法的思维方式。这篇文章我想把这些问题的状态设计思路、转移方程的推导过程、初始化细节、空间优化技巧和踩坑记录一次性讲清楚适合刚学完递归、准备认真啃动态规划的读者也适合已经会写一些DP题但总觉得不够系统的朋友。我尽量只讲方法论和实操细节不堆术语不做“一看就会、一写就废”的那种空谈。1. 动态规划的基本框架状态、转移、初始化1.1 状态给“局面”拍照动态规划的第一步不是急着找公式而是先想清楚一个问题我手上现在掌握什么样的情况才能唯一确定接下来该怎么做这个“情况”通常会成为状态。比如找零钱问题当前金额就是局面因为无论之前用了多少枚硬币只要剩余金额相同未来能做出的最优选择一定相同。比如最大连续子序列和状态是“以某个位置结尾”因为一旦确定结尾位置就不需要管这个子序列从哪里开始只需要知道它之前累加的结果。再比如0-1背包状态是“已经处理到第几件物品、当前还剩多少容量”这两条信息缺一不可。我习惯把状态理解成给一个局面拍一张快照快照里包含的参数越少越好但必须保证无法再区分不同历史时未来的决策是一样的。这个“少而全”的平衡点是DP状态设计的核心。初学者最容易犯的错是状态定义过粗比如找零钱只写“金额”却不考虑“剩余金额”和“已用硬币数”之间的因果关系或者状态定义过细把每一步用了哪枚硬币都记录进去结果状态变成全排列无法合并子问题。1.2 转移描述局面怎么变有了状态第二步要回答“局面是怎么一步步走到现在的”。这个“怎么走到”就是转移方程。写转移方程时我常用一个很朴素的问法站在当前状态我上一步做了什么找零钱问题的答案是“我最后放进去了一枚某面额的硬币”所以当前金额的最少硬币数是由“更小的金额的最少硬币数再加一枚”产生的。最大连续子序列和的答案是“当前元素要么自己重新开头要么拼在前一个最优连续段的末尾”所以才有那个经典的二选一。0-1背包的答案是“我面对当前物品时要么不装它要么腾出重量把它装进去”于是转移两端自然出现。转移的方向也很重要。自底向上填表要保证计算当前状态时依赖的状态已经算完自顶向下递归则要保证没有环状依赖否则会无限递归。判断标准就一条转移涉及的参数是否始终朝着“规模更小”的方向推进。如果是递推表和记忆化递归都能做如果不是说明状态设计有问题需要返工。1.3 初始化边界值的另一种说法初始化不是单独背下来的而是状态定义在“最小局面”下的自然结果。找零钱的dp[0]等于0是因为“金额为0时不需要任何硬币”最长上升子序列的dp[i]初始化为1是因为“每个元素本身就能成为一个长度为1的上升子序列”背包的dp[0][j]等于0是因为“一件物品都没放价值自然是0”。一个很常见的错误是把极大值、极小值、0、1这几种初始化混用。我自己的经验是先把递推公式在纸上写出来再把几个边界情况代入验算比如金额为0、序列为空、容量为0。代入后如果结果与常识不符多半是初始化错了。初始化错的典型表现是小规模样例能过规模稍大就完全不对原因在于错误会顺着递推关系层层放大。2. 找零钱第一次用DP解决“选择”问题2.1 问题描述与暴力递归找零钱问题是这样的给定一组硬币面额比如1、5、11再给一个总金额比如15问最少用几枚硬币能凑出这个金额硬币可以重复使用。我第一次看到这道题时第一反应是贪心每次先用最大面额去凑11加4个1得到5枚。可最优解明明是3枚5元硬币。贪心之所以会翻车是因为局部最大的选择会破坏整体最优。这时就需要一种能“回头比较”所有可能方案的方法动态规划正好能提供这种能力。最直观的写法是暴力递归定义f(amount)表示凑出amount需要的最少硬币数。如果amount等于0返回0否则枚举每一种硬币c如果c不超过amount就尝试f(amount - c) 1最后取最小值。这个递归是正确的但非常慢因为f(amount)会被反复计算很多次。举例来说f(15)会去算f(14)、f(10)、f(4)而f(14)又会去算f(13)、f(9)、f(3)子问题大量重叠指数级膨胀。2.2 从递归改造成填表暴力递归慢是因为同一个子问题被重复求解。解法也很朴素把每个金额对应的结果存起来算过就不再算第二遍。这就是记忆化递归再进一步直接把数组从下标0开始递推填满就是标准动态规划。用数组dp[i]表示凑出金额i需要的最少硬币数初始化dp[0]0其余为无穷大。然后遍历i从1到amount对于每个硬币c如果c不超过i就更新dp[i]min(dp[i], dp[i-c]1)。最后dp[amount]就是答案如果它仍然是无穷大说明凑不出来返回-1。def coin_change(coins, amount): dp [float(inf)] * (amount 1) dp[0] 0 for i in range(1, amount 1): for c in coins: if c i: dp[i] min(dp[i], dp[i - c] 1) return -1 if dp[amount] float(inf) else dp[amount]这段代码的复杂度是O(amount乘以硬币种数)空间是O(amount)。实际使用时要注意amount可能是0此时dp数组长度是1直接返回0即可硬币面额也可能大于amount循环里的if自然会跳过不需要额外处理。2.3 为什么硬币无限也可以套用背包思想找零钱本质上是“物品数量无限”的背包问题也就是完全背包问题的变形。硬币就是物品金额就是容量每枚硬币的价值是1目标是总重量等于容量时价值最小。因为硬币可以任意重复使用所以递推时不需要限制“每个硬币最多一次”这也是它和0-1背包最大的区别。后面聊到0-1背包时我会仔细对比两者循环顺序的差异。这道题还有一个容易忽略的点硬币面额的顺序与答案无关。无论你先枚举金额还是先枚举硬币最小数量都不会变因为这里只关心“用了多少枚”不关心“先放哪一枚”。所以找零钱的循环顺序相对宽松给初学者的压力也小一点。等需要统计“具体怎么凑”时顺序问题才真正变得敏感。2.4 补充统计凑法数量时要注意排列与组合如果把问题改成“有多少种凑法”状态定义基本不变但转移方程要从“取最小值”变成“方案数求和”dp[i] sum(dp[i - c])初始化dp[0]1表示空集是一种凑法。这时候循环顺序就非常关键了。如果外层遍历金额、内层遍历硬币得到的是排列数比如用1、2、3凑3元会同时统计“12”和“21”因为同一金额在不同阶段会反复使用不同硬币。如果外层遍历硬币、内层遍历金额得到的是组合数因为每枚硬币被“固定”下来后就不会再回头考虑它的顺序。我在实际练习中踩过这个坑题目明明要求组合数我却用排列数写法交上去样例只有一个所以没被发现换一组数据立刻多算了很多。所以拿到题先确认顺序重不重要再决定两层循环的摆放方式。3. 最大连续子序列和一维DP的最佳入门3.1 问题定义与暴力做法题目本身一句话就能说清给定一个整数数组找出和最大的连续子数组返回这个最大和。经典例子是[-2, 1, -3, 4, -1, 2, 1, -5, 4]最优子数组是[4, -1, 2, 1]和是6。暴力做法很好想枚举所有可能的起点和终点两层循环算出所有子数组和取最大值复杂度O(n^2)。数据量一大就会超时而且这个问题的结构非常适合DP不需要用更复杂的数据结构。说它是“一维DP的最佳入门”是因为它的状态只有一维转移方程只有一行甚至连完整DP表都不用开用一个变量就能滚动出答案。3.2 状态转移方程的推导关键一步是重新定义状态不要想着“整个数组的最优子段”而是想“以第i个元素结尾的最大连续子数组和是多少”。为什么这么定义因为只有确定了结尾位置才能描述“上一个元素到底有没有被包含进来”。设dp[i]表示以nums[i]结尾的最大子数组和。那么当我站在元素i面前时只有两种选择要么把nums[i]接到前一个最优连续段的末尾也就是dp[i-1] nums[i]要么重新开始一段也就是只有nums[i]自己。取两者较大值就是最优。所以转移方程为 dp[i] max(nums[i], dp[i-1] nums[i])。这个方程背后的直觉有点像“找工作要不要接受前一家公司的经验加成”如果前面积累的收益是正数带上它更赚如果是负数不如清零重来。正是这个“负数宁可不带”的规则保证了段之间的连续性不会被无关元素破坏。3.3 代码、复杂度与边界处理理想情况下我们甚至不需要开完整数组因为dp[i]只依赖dp[i-1]。用一个cur变量保存“以当前位置结尾的最大和”再用best变量保存历史最大值即可空间降到O(1)。def max_subarray(nums): if not nums: return 0 cur nums[0] best nums[0] for x in nums[1:]: cur max(x, cur x) if cur best: best cur return best边界处理有两个很容易出错的地方。第一空数组没有定义最大和通常返回0或抛异常具体看题目要求。第二数组全为负数时cur和best会一路取到最大值比如[-5, -1, -3]的答案是-1而不是0。很多新手会把best初始化为0结果全负数组直接得0这就不对了。正确做法是让best等于第一个元素从第二个元素开始扫描。4. 最长上升子序列从 O(n²) 到 O(n log n)4.1 题目背景与状态定义最长上升子序列Longest Increasing Subsequence简称LIS要求在一个无序序列中找出最长的严格递增子序列子序列不要求连续但必须保持原数组的相对顺序。比如[10, 9, 2, 5, 3, 7, 101, 18]答案可以是[2, 3, 7, 101]长度是4。状态定义和最大连续子序列和很像设dp[i]表示以nums[i]结尾的最长上升子序列长度。同样强调“以i结尾”是为了让每个状态都能清晰知道“上一个元素是谁”。唯一不同是最大连续子序列和只能把当前元素接到前一个相邻元素后面而上升子序列可以接到前面任意一个比当前元素小的元素后面。4.2 经典DP的完整实现转移方程可以从定义直接读出dp[i]等于所有满足j小于i且nums[j]小于nums[i]的dp[j]中的最大值再加1。初始化时每个dp[i]都等于1因为单元素子序列必然是上升子序列。def length_of_lis(nums): if not nums: return 0 dp [1] * len(nums) for i in range(len(nums)): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp)这个版本的时间复杂度是O(n^2)空间是O(n)。写的时候要注意内层循环必须遍历所有j而不是只看i前面紧挨着的那个元素否则会漏掉不连续递增的情况。比如[3, 1, 2]只看前一个是2的dp值会漏掉从1接上2的可能性只有遍历j1时nums[j]1小于2dp[1]1才能算出dp[2]2。4.3 贪心 二分的优化思路O(n^2)在n达到十万级别时撑不住需要优化到O(n log n)。优化思路很有意思不直接求“以谁结尾的最长长度”而是维护一个数组tailstails[len]表示“长度为len的上升子序列中末尾元素的最小值”。为什么这个数组有用因为如果有两条长度相同的上升子序列末尾更小的那条更有潜力继续变长就像竞争岗位时手里资源更省的人更容易活下来。遍历原始数组时对每个元素x在tails里找到第一个不小于x的位置把它替换成x如果x比tails里所有元素都大就追加到末尾。最终tails的长度就是答案。import bisect def length_of_lis(nums): tails [] for x in nums: pos bisect.bisect_left(tails, x) if pos len(tails): tails.append(x) else: tails[pos] x return len(tails)这里有个细节要多说两句。题目要求严格递增所以重复元素不能接在相同元素后面应该替换掉第一个不小于x的位置也就是bisect_left如果改成非严格递增就应该用bisect_right把相等的元素也当作“可以追加”这样重复值才能算进长度。这个差异很隐蔽我当年在某个在线评测平台上就因为这个二分函数选错连挂三次。4.4 重建具体上升序列如果题目只问长度上面的优化已经足够了。但如果要输出具体子序列二分方案维护的tails数组并不能直接还原路径因为tails在替换过程中并没有保留“谁把谁顶替掉”的关系。这时有两个选择一是用O(n^2)的DP额外开一个pre数组记录每个状态是从哪个j转移过来的最后从最长长度的位置一路往前回溯二是仍然用二分优化但额外维护一个idx数组记录每个元素在tails中的位置再配合原数组反推。考虑到大多数场景下n不会特别大我建议先掌握O(n^2)pre数组的写法因为思路清晰、不容易写错。只有在明文要求O(n log n)或数据量极大时才去折腾二分重建法。训练时用“长度”版本练优化用“输出序列”版本练回溯分开练反而更高效。5. 最长公共子序列与最长公共子串两个序列DP的左手和右手5.1 最长公共子序列的状态设计最长公共子序列Longest Common Subsequence简称LCS问题给定两个字符串要求找出同时是两个字符串子序列的最长长度。子序列不要求连续比如“ABCBDAB”和“BDCABA”的最长公共子序列可以是“BCBA”长度是4。这个问题之所以经典是因为状态变成二维设dp[i][j]表示字符串A的前i个字符和字符串B的前j个字符的最长公共子序列长度。字符串下标偏移一位是为了给i0或j0留出“空串”边界。转移规则是逐字符比较。如果A的第i个字符等于B的第j个字符那么这个字符一定能拼在之前已经匹配好的子序列后面所以dp[i][j]dp[i-1][j-1]1。如果不相等说明当前这两个字符不能同时进入子序列答案只能从前一状态继承取dp[i-1][j]和dp[i][j-1]的较大值。用一个不是很严谨但非常形象的类比两个字符相等就“结婚”不相等就只能看两人各自前一段谁更优秀。def lcs(a, b): m, n len(a), len(b) dp [[0] * (n 1) for _ in range(m 1)] for i in range(1, m 1): for j in range(1, n 1): if a[i - 1] b[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]5.2 回溯出完整子序列如果只要求长度上面代码已经结束。但很多题目会追问“最长公共子序列是什么”这就需要回溯。方法是从dp表的右下角出发倒着走回左上角。当前字符相等时说明这个字符被计入了子序列记录它并向左上移动不相等时比较dp[i-1][j]和dp[i][j-1]谁大就往谁那侧移动两者相等时可以任选一个方向。最后把记录下来的字符反转就是答案。# 接在上面的 dp 计算之后 res [] i, j m, n while i 0 and j 0: if a[i - 1] b[j - 1]: res.append(a[i - 1]) i - 1 j - 1 elif dp[i - 1][j] dp[i][j - 1]: i - 1 else: j - 1 return .join(reversed(res))回溯时要注意如果dp[i-1][j]和dp[i][j-1]相等选择哪边都可能得到正确长度但不同内容。所以当题目只要求“任意一个最长公共子序列”时回溯写起来可以随意如果要求字典序最小则需要额外规定优先级。这个细节很容易被忽略。5.3 最长公共子串从“不连续”到“必须连续”最长公共子串Longest Common Substring和最长公共子序列只差两个字思路却要重新调一下。因为是子串所以匹配的字符必须连续一旦不连续之前积累的长度立即作废。dp[i][j]定义保持不变但转移逻辑变成如果A的第i个字符等于B的第j个字符则dp[i][j]dp[i-1][j-1]1否则dp[i][j]直接写0表示以这两个字符结尾的公共子串长度为0。整体答案不再像LCS一样固定在dp[m][n]而是所有dp值里的最大值同时要记录最大值的下标方便截取具体子串。def longest_common_substring(a, b): m, n len(a), len(b) dp [[0] * (n 1) for _ in range(m 1)] best 0 end_index 0 for i in range(1, m 1): for j in range(1, n 1): if a[i - 1] b[j - 1]: dp[i][j] dp[i - 1][j - 1] 1 if dp[i][j] best: best dp[i][j] end_index i else: dp[i][j] 0 return a[end_index - best: end_index] if best else 这段代码里end_index记录的是A中当前最优子串结束位置的下一个字符下标所以最后切片时用end_index - best作为起点。实际操作中边界、索引、切片的下标非常容易错建议在本地运行几次带样例的测试把所有下标算清楚再提交。5.4 两个问题的一页纸对比到这一步把两个问题放在一起看差异非常清晰对比项最长公共子序列最长公共子串连续性要求不要求连续要求连续相等字符转移dp[i-1][j-1] 1dp[i-1][j-1] 1不等字符转移max(dp[i-1][j], dp[i][j-1])直接写0答案位置固定在dp[m][n]全局所有位置取最大值典型应用文本diff、序列比对代码查重、字符串匹配这张表值得抄在笔记本上。我见过不少同学把两个问题的转移方程混着写最典型的表现是子串问题用了max导致一旦中间断开前面的长度还能残留结果答案“看起来很长”实则片段不连续。记住一句话子串是“断了就清零”子序列是“断了还能继承”。6. 0-1背包最典型的“装与不装”6.1 问题定义与二维状态表0-1背包的描述是有n件物品每件物品有重量w[i]和价值v[i]背包容量是W每件物品只能选择装一次问能装下的最大总价值。它和找零钱最大的不同是“每件物品只能用一次”。这个限制看起来很小但会让循环方向发生根本变化如果不理解背后的原因代码就会在“正序”和“逆序”之间反复翻车。状态定义比较自然dp[i][j]表示从前i件物品中挑选容量不超过j时能获得的最大价值。第一维“前i件”用来控制可选物品范围第二维“容量j”用来表达当前背包余量。初始化时无论容量是多少一件物品都不选价值都是0所以dp[0][j]0。6.2 转移方程与初始化细节对于第i件物品我只有两种选择不装它继承上一件物品在同样容量下的最优值dp[i-1][j]装它需要腾出w[i]的重量获得v[i]的价值即dp[i-1][j-w[i]]v[i]前提是j不小于w[i]。取两者最大值就是dp[i][j]。二维写法先写出来更容易理解def knapsack_2d(weights, values, W): n len(weights) dp [[0] * (W 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(1, W 1): if j weights[i - 1]: dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] values[i - 1]) else: dp[i][j] dp[i - 1][j] return dp[n][W]这个版本的逻辑很直白建议作为学习的第一版。初始化时dp表里所有元素默认是0等于天然处理了“容量为0”和“物品为空”的边界。需要注意的是如果某些物品的重量为0转移时需要照顾到重量为零的物品可以无限叠价值这会变成一个特殊的完全背包问题大多数题目会约定重量大于0但也值得看一眼题目条件。6.3 滚动数组优化为什么必须逆序遍历二维DP的时间是O(nW)空间也是O(nW)。当W达到很大时二维数组吃不消需要把空间压成一维数组dp[j]含义是“容量为j时当前能获得的最大价值”。一维优化的关键完全在于内层循环必须从大到小遍历容量。原因很简单dp[j-w[i]]必须是上一件物品的状态而不是当前物品更新过后的状态。如果从小到大遍历当计算第i件物品的dp[j]时dp[j-w[i]]可能已经被第i件物品更新过相当于一件物品被反复使用这就违背了“每件最多一次”的约束反而变成了无限使用。逆序遍历可以保证dp[j-w[i]]仍然来自上一轮因为容量小的位置在本次循环中还没有被当前物品覆盖。def knapsack_1d(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]如果题目改成完全背包即每件物品可以不限次数使用内层循环就从正序遍历这样才能让当前物品反复参与更新。这也能反过来验证我前面说的找零钱因为硬币无限内层循环顺序不敏感但背包因为物品有限顺序成了天堑。建议大家拿一个具体的三件物品例子手动演算一遍正序和逆序的区别比背十遍结论都管用。6.4 如何还原选中的物品一维数组只保存了最优值丢掉了“从哪来”的信息。如果要输出选中的物品最好保留完整的二维DP表然后从右下角开始回溯# 假设已经用二维 dp 填好表 selected [] j W for i in range(n, 0, -1): if j weights[i - 1] and dp[i][j] dp[i - 1][j - weights[i - 1]] values[i - 1]: selected.append(i - 1) j - weights[i - 1]回溯逻辑是如果dp[i][j]恰好等于“装下第i件物品”的状态就说明最优方案里包含它否则这个值一定等于不装它的状态dp[i-1][j]就继续往前看。实际使用时要注意如果物品价值恰好都是0或出现并列最优回溯出的一组选择可能是其中一种不一定唯一但一定是合法的。这类“只求一组可行解”的题目通常会在题目里注明“任意一组均可”。6.5 找零钱、完全背包、0-1背包的三方对比这三个问题经常被放在一起考因为它们本质是同一族问题。下面这个对比是我刷完几十道背包变体之后总结出来的问题物品使用次数目标外层循环内层循环0-1背包每件最多一次总价值最大物品容量逆序完全背包每件无限次总价值最大物品容量正序找零钱最少硬币每枚无限次硬币数量最少金额或硬币均可金额或硬币均可最后一行的“均可”也有适用前提就是只求最小数量不关心顺序。一旦改为“统计凑法方案数”循环顺序就必须按照组合数的规则来摆。理解了这一层再看很多背包型数据结构题能一眼看出它到底属于哪种变体。7. 实战排查动态规划里最容易踩的六个坑7.1 初始化写错整个DP表跟着歪我的经验是初始化错误通常不是写错一个数字而是把状态定义和边界条件错配。比如LCS的dp表把第一行第一列初始化为1就会把所有结果整体加偏移找零钱把dp[0]初始化为1会让方案数比正确值多出很多。排查方法很简单用一个极小的样例手动填一遍表看第一行、第一列、第一次循环的结果是否合理。如果第一遍填表就“看起来不对”不用怀疑先回去读状态定义。7.2 滚动数组的遍历顺序搞反背包问题中正序和逆序的后果是截然不同的逆序是0-1背包正序是无限使用物品。我自己在写代码时会把“容量逆序”这四个字直接写在注释里。如果提交后发现答案比预期大优先怀疑这里因为正序会让同一件物品被反复累加价值结果必然偏大且偏大的程度会随容量上限迅速膨胀。7.3 最长公共子串的答案存错位置子串问题的答案不是固定在某一个角落而是整个dp表的全局最大值。我有几次在写LCS之后顺手改子串题只改了转移方程忘了记录best和终止下标结果返回的是dp表右下角的值。那个值往往比真实答案小因为最后两个字符一旦不相等右下角就会被强制写成0。排查这类问题直接在计算过程中打印每次更新best时的行列号能快速定位。7.4 二分查找的边界条件LIS二分优化里的bisect_left和bisect_right选择直接决定了严格递增和非严格递增的结果。选错一次正确性就错一半。我个人的检查方法是把数组改成[1, 1, 1]如果是严格递增正确答案是1用bisect_right就会错误地得到3非严格递增则相反。这种特例输入应该在提交前主动构造出来测一遍。7.5 组合数写成排列数找零钱方案数里外层遍历硬币是组合外层遍历金额是排列。如果题目要求组合数而写成排列结果会偏大。判断方法是在草稿上用两个不同顺序的面额各手动数一遍比如硬币1、2凑3元组合数只有两种排列数会有重叠。一旦发现答案含有“12”和“21”这种顺序相反的计数就要调整循环层级。7.6 复杂度失控以后怎么救动态规划不是万能钥匙状态数过于庞大时同样会超时或超空间。比如0-1背包容量非常大而物品数量很小二维DP就扛不住这时可以考虑把“价值”作为DP维度求“达到某个价值需要的最小容量”再用总容量去比较。找零钱如果硬币面额很少但金额巨大可以考虑用贪心配合DP剪枝不过这类优化对初学者偏难不建议一上来就走偏门。先把最标准的写法练熟遇到优化需求时再针对状态维度动手。我个人在实际操作中还有一个很笨但有效的习惯每学一个DP问题就把它的“状态定义”“转移方程”“边界条件”“常见变体”写成一张卡。卡不用很长但必须用自己的话写清楚。学完这六个问题再回头看你会发现它们本质上只有两件事一是把问题压缩成几个关键参数二是明确每一步有哪些选择。参数决定状态表的长相选择决定转移方程的写法。想通这两点后面再遇到区间DP、树形DP、状态压缩DP上手速度会快很多。
