很多人学动态规划第一轮啃概念觉得“最优子结构、无后效性、重叠子问题”说得头头是道合上书就废。真正拿到一道新题状态定义想一小时转移方程憋不出来边界条件一写就错。这篇《动态规划理论基础II》不打算再抄一遍教材而是想把理论和实操中间那层断层补上状态到底怎么定义、转移方程怎么推、经典模型怎么归类、出了问题怎么调。适合的读者是已经大概知道DP是什么、但做题还经常卡壳的人。如果你是零基础建议先去把递归、记忆化搜索和斐波那契这类例子弄熟再回来看这篇。很多人以为DP难在转移方程其实我刷了这么多题之后的感觉是90%的卡壳都出在状态定义上。状态是动态规划的地基地基歪了后面全是空中楼阁。这篇我会用大量具体例子把我平时做题时的思考过程直接摆出来尽量不写一句正确的废话。1. 状态设计动态规划真正难住人的第一步1.1 状态定义的本质你在为子问题拍一张快照状态到底是什么我的理解是状态是你对某个子问题的一个“快照”它用几个参数把解决这个问题所必须知道的信息浓缩起来结果值就是这个快照对应的最优答案。为什么要这么想因为动态规划本质上是对递归搜索的缓存只有参数完全相同的子问题才能共用缓存。所以状态定义的第一原则是参数要包含“未来决策所需的全部信息”同时又尽量少带无关信息。拿最长上升子序列来举例。假设我想定义dp[i]表示“前i个元素的最长上升子序列长度”够不够不够。原因是后面元素能不能接上取决于当前子序列的末尾值是多少而“前缀的最长值”不一定是“尾巴最有机会接新元素”的那一个。比如数组是[2, 5, 3, 7, 4]只看前3个元素最长上升子序列是[2, 5]长度2以3结尾的子序列是[2, 3]长度也是2。但后面的4能接在3后面却不能接在5后面。如果状态里不记录“以谁结尾”这个信息就丢了。所以更准确的状态是dp[i]以第i个元素结尾的最长上升子序列长度答案是对所有dp[i]取最大值。这个例子的价值在于它展示了一个思考模板每次写状态之前问自己一句“决策最后一步的时候我需要知道关于之前的哪些信息”。需要知道处理到哪个位置这是一个维度需要知道当前结尾的值、剩余容量、已用次数这些是追加的维度。额外维度不是拍拍脑袋加上去的而是为了保证无后效性——所有会影响未来决策的信息都必须收进状态里。1.2 从题目条件反推状态要有几维我刚开始学DP的时候最喜欢猜状态看到数字就写dp[n]结果经常把一维用到底。后来养成一个习惯先看输入参数的数量。如果输入只有一个序列状态通常至少一维如果输入里有一个容量、一个上限、一个次数约束你就要认真考虑是不是该再加一维。因为状态维度的本质就是递归搜索树上一个节点需要记录哪些参数。举个例子0-1背包问题N个物品每个物品有重量wi和价值vi背包容量W求能装下的最大价值。搜索树上一个节点需要知道两件事当前处理到第几个物品了包里还剩多少容量。这就是二维状态dp[i][j]表示前i个物品里选一些放进容量j的包能拿到的最大价值。同样的题目如果加一个限制“总共最多选K个物品”那必须再开一维变成dp[i][j][k]表示前i个物品、用了j容量、已经挑了k个物品时的最大价值。规律很简单多一个会被限制的条件通常就多一维状态。不过也要提醒一句状态维度不是越大越好。每多一维时间和空间可能就多一个数量级。真正见功夫的是信息压缩题目里每个物品有编号但背包问题根本不需要知道选的是哪几个只需要知道考虑了多少个、用了多少容量。把“具体集合”压缩成“已考虑的个数”这就是从指数级搜索降到多项式DP的关键。2. 转移方程是怎么一步一步推出来的2.1 永远先想“最后一步”是什么转移方程不是灵光一现它描述的是当前这个状态可以从哪些前驱状态通过一次决策到达。我自己的习惯是“以终为始”——不要从dp[1]开始想递推到dp[n]而是反过来想假设当前状态已经算好了它的值是从哪些来源拼出来的。一维爬楼梯是最简单的示范。要到第n阶最后一步只能是从n-1阶迈一阶或者从n-2阶迈两阶。这两个来源互斥且完备所以dp[n] dp[n-1] dp[n-2]。这个例子太简单但思路通用。再看一个稍微有味道的题零钱兑换给定总额amount和硬币面额数组coins求凑出这个总额最少需要几枚硬币。凑出x元最后一步必然是选择一枚面额为c的硬币那么前一个状态就是“凑x-c元”。把所有c都枚举一遍取最小得到dp[x] min(dp[x - c] for c in coins) 1这里的前驱不是固定的一个而是一组候选由最后一个决策决定。这正是转移方程最常见的形态枚举最后一步的所有可能从各个前驱状态取最优或求和。最长上升子序列也一样。dp[i]表示以第i个元素结尾的LIS长度那么倒数第二个元素是某个下标j必须满足j i且nums[j] nums[i]。于是dp[i] max(1, max(dp[j] 1 for j in range(i) if nums[j] nums[i]))所有转移方程本质上都在做同一件事枚举“从哪个状态来”。你把这个逻辑想通了就不再需要背任何DP模板。2.2 边界条件与循环顺序两个让人头大的细节边界条件写不对大概率是没想清楚“空状态”的含义。我的经验是不要把所有dp都统一初始化成0必须先明确每个格子代表的是“合法状态”还是“不可达状态”。求最大值时不可达状态常设成负无穷或-1求最小值时不可达状态常设成正无穷只有真正可以当作起点的状态才单独初始化成0、1或其他具体值。举一个典型的反例。求最少跳跃次数到达数组末尾如果你把所有dp初始化为0转移时做min操作那么所有状态都会从0这个“假合法”状态取到最小值答案永远是0。正确做法是把dp[0]初始化为0其余初始化为很大的数比如float(inf)然后当某个状态能从更少步数的合法状态跳过来时才更新。这层理解比背“初始化为INF”更重要。循环顺序也一样。动态规划本质上是在一张有向无环图上按拓扑序填表一个状态依赖谁就要保证在计算它之前被依赖的格子已经被填好。爬楼梯从2到n正着循环因为dp[i]依赖dp[i-1]和dp[i-2]有些倒推问题依赖dp[i1]那就要从n-1到0倒着循环。区间DP必须外层按区间长度枚举因为长区间依赖短区间0-1背包必须容量倒序枚举因为要避免当前物品被重复使用。这些都不是需要死记的口诀而是“依赖先算好”的自然结果。3. 三大经典模型背后的统一逻辑3.1 背包模型容量与价值之间的权衡背包问题之所以经典是因为它抽象了一大类资源分配问题手里有总量有限的资源一大堆候选项目各有代价和收益怎么选收益最大。0-1背包、完全背包、多重背包的区别本质只是每个物品能用几次。0-1背包的转移很多人都会写for i in range(1, n 1): for j in range(capacity, weight[i] - 1, -1): dp[j] max(dp[j], dp[j - weight[i]] value[i])这里dp[j]表示容量为j时能拿到的最大价值。为什么要倒序枚举容量因为正序的话你计算dp[j]时读到的dp[j - weight[i]]可能已经被这一轮外层循环更新过了它已经包含了“选入第i个物品”的结果于是同一轮里你能把同一个物品塞进去两次。倒序能保证读到的永远是上一层的老值也就是说每件物品最多被选一次。完全背包和0-1背包的转移几乎一样唯一的区别是内层循环改成正序for j in range(weight[i], capacity 1): dp[j] max(dp[j], dp[j - weight[i]] value[i])用刚才的逻辑解释就通了正序循环时dp[j - weight[i]]可能是刚刚被本轮更新过的新值它已经包含了使用第i个物品的可能所以一个物品可以被反复使用正好符合“无限量供应”的语义。你看根本不用背哪个背包正序哪个倒序把覆盖顺序想明白就行了。多重背包是另一个故事。每个物品最多用cnt次朴素做法是再加一层循环枚举使用次数复杂度直接乘上一个k。经验做法是二进制拆分把cnt拆成1、2、4、8、……以及最后剩下的余数每一份都当成一个独立的新物品然后跑0-1背包。为什么可行因为任何0到cnt之间的整数都能由这些2的幂子集组合出来。这个办法理解了以后竞赛里处理多重背包就很顺手。3.2 区间DP先合并小的再合并大的区间DP是另一类特别常见的模型状态通常是dp[l][r]表示对区间[l, r]做某种处理后的最优值。最经典的例子是石子合并有一排石子堆每次只能合并相邻两堆代价是这两堆重量之和问合并成一堆的最小总代价。关键在于最后一步整堆石头一定是由左右两部分合并来的所以转移方程是枚举分界点kdp[l][r] min(dp[l][k] dp[k 1][r] sum(l, r) for k in range(l, r))其中sum(l, r)是区间[l, r]的总重量是最后一次合并付出的代价。代码结构基本固定先枚举区间长度len再枚举左端点l算出右端点r l len - 1最后枚举分界点k。三重循环复杂度O(n^3)。为什么外层必须枚举长度因为dp[l][r]依赖的所有子区间长度都小于len只有按长度从小到大才能保证需要的值都已经算好。矩阵链乘问题也是同一个骨架dp[l][r]表示第l个到第r个矩阵连乘的最少乘法次数转移里多了一个维度参数p代价是p[l-1] * p[k] * p[r]。很多看起来完全不同的题比如戳气球、括号匹配、多边形剖分最后都是这个模式。所以我建议你把区间DP的“长度-左端-分界点”三层循环写成肌肉记忆在此基础上理解每道题自己的代价函数是什么。3.3 状态机DP把“当前处于什么阶段”写进状态有些序列DP题除了位置维度之外还隐含一个“当前处于什么状态”的信息。最典型的就是打家劫舍一排房子不能偷相邻的两家问最大收益。如果只定义dp[i]表示前i家的最大金额你会发现转移很别扭因为你不知道第i家到底偷没偷也就不知道第i1家能不能偷。解决方案是加一维dp[i][0] max(dp[i-1][0], dp[i-1][1]) # 不偷第i家 dp[i][1] dp[i-1][0] nums[i] # 偷第i家0表示“第i家没偷”1表示“第i家偷了”。这个状态定义就是一个微型状态机节点是0/1转移边是“从某个状态走到另一个状态”。股票买卖问题更好理解。每天结束时你手里要么持有股票要么不持有。dp[i][0]表示第i天结束时手上没有股票的最大现金dp[i][1]表示第i天结束时持有股票的最大现金dp[i][0] max(dp[i-1][0], dp[i-1][1] price[i]) dp[i][1] max(dp[i-1][1], dp[i-1][0] - price[i])持有状态可以继续持有也可以卖掉变成不持有不持有状态可以继续观望也可以买入变成持有。限制“最多交易k次”时再加一维k买入动作消耗一次交易次数。状态机DP的价值在于把题目里用自然语言描述的限制显式地变成状态维度之后转移就是单纯地在状态图上走边。这个思想再往前一步还能处理允许冷却期、包含手续费等一系列股票衍生题。4. 实战前必看DP调试三板斧与常见错误速查4.1 先判断能不能用DP三个必要条件很多人拿到题就开始写状态其实第一步应该判断这题适不适合DP。三个必要条件是最优子结构、重叠子问题、无后效性。最优子结构指原问题的最优解可以由子问题的最优解组装出来重叠子问题指同一个子问题会被多个更大的问题反复使用无后效性指一旦某个状态的值确定后面怎么决策都不受到达该状态的具体路径影响。用零钱兑换做例子很合适。硬币面额1、5、11要凑15。如果贪心每次都拿最大的11得到的是4枚硬币但最优解是5553枚。为什么贪心失效因为局部最优推不出全局最优。DP能行是因为“凑15的最少硬币数”可以由“凑14、凑10、凑4”这三个子问题各加1枚得到子问题之间重叠且独立。这三条都满足DP就是合适的工具。如果问题有重叠子问题但不存在最优子结构那DP也未必成立。比如求最长简单路径路径不能重复经过节点子路径的最优选择会互相影响这时候DP就失灵了。所以我的例行公事是拿到题目先自言自语两句话——这个全局最优能不能拆成子问题最优后面决策还需要知道前面哪些破事如果都说得通再动笔写状态。4.2 调试DP三板斧第一板斧是打表。写完转移方程先输出整个dp数组或dp矩阵逐行看。二维表就一张张打印看哪些格子是无穷大、哪个格子是起点、每个格子是从哪个格子转移来的。很多时候你一眼就能看出“这个值是从一个不可能的状态推来的”。第二板斧是造最小用例。n等于1、等于2、空数组、只有一堆石子这些边界情况手算答案特别容易跑完程序一对比就知道边界对不对。小数据错了再用打表定位效率极高。第三板斧是暴力对拍。写一个纯递归或直接枚举所有方案的暴力方法不关心复杂度然后生成几十组n不超过8的小随机数据把暴力结果和DP结果逐个比对。这个方法极其土但极其有效。我个人的习惯是每写一个DP题只要不是考场赶时间都会顺手写个暴力对拍。一旦发现结果不一致打印DP表和暴力的搜索路径几乎没有定位不了的问题。4.3 常见错误速查表错误现象常见原因检查方向求最小值结果偏大不可达状态没有设成无穷大或者初始状态没设置检查dp初值和dp[0]的语义求最大值结果偏小不可达状态设成了0但0不是合法起点检查负无穷或-1的设置答案总是差1下标从0还是从1没统一dp[0]含义没想清逐个状态重读定义背包结果变成可以重复选0-1背包内层循环写成了正序回到“覆盖顺序”理解区间DP结果错外层没有按区间长度枚举检查计算顺序是否是拓扑序滚动数组后结果变错压缩维度时覆盖了后面还要用的旧值每次更新前确认旧值是否已被消费表格最后再补一句我的体会初值的本质是“这个状态下还没做任何决策时的信息”。求方案数dp[0]常常等于1因为凑出空集只有一种方案求最少步数dp[0]常常等于0因为原地不用走不可达状态设成极大或极小是为了让min/max操作自动避开它。想明白这些边界条件就不是靠猜了。4.4 空间优化不是炫技是必要的工程意识当转移只依赖上一层的状态时可以把二维数组压成两个一维数组甚至一个数组。滚动数组最经典的应用就是背包空间优化把dp[i][j]压成dp[j]前提是循环方向正确保证更新时读到的还是上一层的值。空间优化后代码看起来更简洁但对“什么时候覆盖旧值”的要求更高所以我建议初学者先写二维版本验证正确后再压维不要上来就写滚动数组然后疯狂debug。再往上走还有状态压缩DP用一个整数bitmask表示一个集合。比如旅行商问题dp[mask][v]表示已经访问过的城市集合为mask当前停在v点的最小花费。这类题的状态本身就是集合维度拆不开只能用mask压缩。这是理论基础的延伸方向先知道有这个东西等真正遇到再把bitmask的几个技巧捡起来。回到开头的那个问题动态规划的理论基础到底在讲什么我现在的答案是只讲两件事状态里存什么状态之间怎么走。状态设计回答前者转移方程和循环顺序回答后者。这两件事想明白了剩下的事情都可以靠调试和练习磨出来。最后分享一个小经验也是我用了很久都觉得很有效的习惯拿到任何一道DP题先在草稿纸上写三行注释——状态定义、转移方程、初始条件然后才开始写代码。这个动作看着傻但它能逼着你在动手之前把所有逻辑漏洞想清楚。动态规划不是靠灵感靠的是把每一步都想明白的耐心。