Skip to content

方法Method

动态规划

施工中 · 内容逐步修订

Dynamic programming

在有限或良基的状态依赖上复用已计算结果的算法设计范式。

从四件物品开始

容量只有 7 的背包,面前有四件各只能取一次的物品:A 的重量、价值为 (1,1),B 为 (3,4),C 为 (4,5),D 为 (5,7)。按单位重量价值从高到低取,会先拿 D,再拿 A,得到 8;B 与 C 合起来却重 7、值 9。局部最划算的一件,可能挤掉更好的组合。

不妨先问一个更小、含义明确的问题:dp[i,w] 表示只用前 i 件、总重量不超过 w 的最大价值。对第 i 件,任何装法都只有不选、选一次两种情况:

dp[i,w]={dp[i−1,w],w<ai,max{dp[i−1,w], dp[i−1,w−ai]+vi},w≥ai.

没有物品时 dp[0,w]=0。按 i 逐行计算,结果为:

已处理物品 / 容量 0 1 2 3 4 5 6 7
无 0 0 0 0 0 0 0 0
A 0 1 1 1 1 1 1 1
A、B 0 1 1 4 5 5 5 5
A、B、C 0 1 1 4 5 6 6 9
A、B、C、D 0 1 1 4 5 7 8 9

为什么这个表可信?对 i 归纳。每个候选都由前 i−1 件的可行装法组成,选第 i 件时又预留了它的重量,所以不会算出不可行的高分。反过来,任意最优装法若没选第 i 件,属于第一项;若选了,删去该件后属于第二项的子问题。两种情况没有遗漏,因而递推值恰为真最优值。这里真正起作用的是状态包含了剩余决策所需的信息,以及转移覆盖了全部情形。

表格只存最优值,还要从分支找回物品。在 (4,7) 选择“不取 D”,到 (3,7) 必须取 C,于是到 (2,3);再取 B,到容量零。得到 B、C,重 3+4=7、值 4+5=9。若两个分支打平,任选一个可恢复一份最优装法;枚举全部最优装法还要处理分叉及输出大小。

这个例子用 5×8=40 个表项代替反复求解的递归子问题。推广到 n 件正整数重量物品、整数容量 W,直接表格花费 Θ((n+1)(W+1)) 次常数成本状态操作。它对容量的数值是多项式,对二进制编码的输入长度却未必如此:写下 W 只需 Θ(log⁡(W+1)) 位。这是伪多项式界,不能只见到二维表就认定算法对输入长度为多项式。

形式陈述 ​

动态规划把序列递推推广为状态集 S 上的方程:每个 s∈S 的值只由其直接依赖 pred(s) 的值组合而成,并为无依赖状态给出基例。若依赖关系是有限无环图,就用拓扑排序确定填表次序。这里画边 t→s 表示计算 s 要读 t 的值,即箭头由依赖项指向使用它的状态;求值按拓扑序前进,递归查找依赖则沿箭头反向展开。拓扑序可以直接由下标给出,不必另行建图、运行排序程序。

记忆化给出自顶向下的具体实现:从目标递归求依赖,完成一个状态就缓存结果。本页的实现保证以状态键包含全部相关输入、结果确定、可达依赖有限无环、各局部计算终止、缓存不淘汰为条件;满足这些条件时,它与同一基例和递推的拓扑填表在共同计算的状态上给出相同值。这不承诺相同的访问集合、栈深、内存布局或成本,也不把任意函数缓存都当作动态规划。更一般地,依赖可以由严格关系 ≺ 给出:若 t∈pred(s) 时总有 t≺s,且 ≺ 是良基的,则可用良基递归确定每个状态值。要得到有限算法,还需目标可达的依赖图有限,每个状态的直接依赖可有效枚举,基例与组合运算能在有限时间完成。良基性本身允许无限多个直接依赖,不能替代这些计算条件。

优化问题常有

F(s)=opta∈A(s){c(s,a)+F(T(s,a))},

这里 A(s) 是状态 s 允许的选择,c(s,a) 是这一步的贡献,T(s,a) 是选择后所依赖的较小状态;先固定这些含义,才有依据决定用最小值还是最大值合并。计数、可达性、概率传播和字符串识别使用相应的加法、逻辑或等运算,并不需要“最优子结构”。若有 N 个可达状态,每个状态检查至多 T 个转移,每次转移、查表及一个状态的初始化和存储均为常数成本,则直接实现需 O(N(T+1)) 时间和 O(N) 存储。大整数计数不能忽略单次加法的位成本。

若状态依赖含环,单纯按表格顺序代入已无定义。一种严格的扩展是先给状态值域配备偏序,再把全部状态方程写成单调算子 F,并明确规定要取的解,例如最小不动点 lfp(F);还需为所用迭代证明收敛到该不动点。任意环状递推方程不会因为“可以反复更新”就自动成为动态规划:解可能不存在、不唯一,或更新根本不收敛。

直觉

动态规划先问“未来究竟需要哪些过去信息”,再把这份充分摘要定义为状态。当两条路径得到同一状态时,它们的后续计算便可合并。状态太少会丢失影响未来的信息,太多则把整段历史原样带入。因此核心工作是证明状态充分、转移完备,并给出合法求值顺序。

动态规划状态依赖与填表顺序
例子与边界

动态规划主动识别并合并相同子问题,以状态表或记忆化避免重复计算;回溯法沿选择树枚举候选,并靠可行性或界限剪枝撤销选择。两者可以组合,但“存在递归分支”并不足以构成动态规划。

背包递推的两个分支都只读上一行,因此可以压成一行;但省去一个下标以后,旧值与新值会共用地址,执行顺序就成了正确性的一部分。

只考虑一件重量 2、价值 3 的物品,容量为 4,初始一维表全零。若容量从小到大更新,先把 dp[2] 设为 3,再用这个刚写入的值计算 dp[4]=dp[2]+3=6,相当于把物品选了两次。从大到小更新时,计算 dp[4] 读到的 dp[2] 仍是上一行的 0,结果为 3;之后才改 dp[2]。逆序不是口诀,而是在原地存储中保留递推依赖的旧版本。

若还要输出选中的物品,仅存最优数值不够;可在二维表记录每个状态采用哪条转移,再从目标状态沿选择倒推。压缩空间后这些历史选择可能被覆盖,需要另存信息或重新计算,不能把数值计算的空间界直接当成完整解重建的空间界。

编辑距离网格把这一区别具体化:完整前缀表能回溯插删替换脚本,滚动行只保留费用。Hirschberg 方法先用前后向费用认证中线切口,再释放数组、递归重建;因此要分别核算工作数组、递归栈和输出。

状态设为“当前价值”却不保留已用容量,通常无法决定背包的后续可行性;反过来,把所有已选集合当作状态虽然充分,却退化为指数枚举。“写出了递推式”只是起点;还必须证明状态确实包含后续所需的全部信息,转移覆盖了所有合法情形,且所选求值规则真能得到指定的解。

最少回文分解给出一个完整的前缀状态实例:枚举所有回文末块,再由前驱表输出真实切点。aaba 否定先取最长回文前缀的贪心;线性时间求好回文半径后,候选切点总数仍可能是二次方,因而预处理变快不等于整个DP变快。

推论与应用

记忆化以需求驱动方式解状态,表格法则按依赖顺序主动求值。动态规划可用于 DAG 最短路、序列比对、背包、矩阵链乘、区间问题、树分解、概率模型与有限时域控制。其中计数、概率与可达性例子也说明,动态规划的主体是状态方程的有效求值,而不是优化问题所特有的“最优子结构”。与分治比较时,应看是否主动合并相同子问题,而不是只看有没有递归:归并排序的两半可以各算各的,Fibonacci 的重复下标则值得缓存。分治也能与动态规划组合,Hirschberg 重建就是例子;两种范式不是互斥分类。与贪心比较时,开头的背包反例说明:只保留一个局部选择需要安全选择证明,不能用“看起来最划算”替代对其余状态的比较。

高级 DP 仍应从状态 DAG 看待,而不是把新技巧当模板名。子集动态规划把 2n 个子集作为节点,树宽 DP把 bag 边界状态沿树分解传播,Color Coding用随机着色压缩“互异顶点”约束;三者分别以指数状态、结构参数和随机化换可解性。四俄罗斯与字级并行则批量执行一组有限转移,只改善每条边的处理成本,不改变状态依赖正确性。

另一些加速减少的是候选转移。Monge 四点不等式可证明最左切点单调,分治 DP 优化再据此收紧搜索范围;若转移还能展开为直线查询,直线下包络利用斜率与查询顺序维护候选。每一种省略都要对应自己的结构证明。

固定位费用LZ77解析提供另一种完整转移压缩:同一距离价格档先求最长可复制前缀,再把相同长度费用的一段目的位置交给区间最小值。每个合法长度仍被某个区间覆盖,所省的是枚举工作而不是未经证明地丢弃选择;只有码价不随此前解析改变时,单独记当前位置才足以决定剩余问题。

单元终结任务:把一张依赖图算成答案 ​

给定顶点 s,a,b,c,t,x,y,弧及费用为

s→a:2,s→b:5,a→b:−1,a→c:4,b→c:1,b→t:5,c→t:2,s→x:7,x→y:1.

要求从 s 到 t 的最小费用及一条达到它的路径。状态 d[v] 表示从 s 到 v 的最小费用,d[s]=0;其他顶点取所有入弧候选 d[u]+w(u,v) 的最小值。边 u→v 既是输入弧,也是“u 的值先于 v”的依赖弧。请交付下面四项,而不只写最终数字:

  1. 计算。 给出一个拓扑序,列出全部七个状态值和取最小值的前驱。从 t 倒走前驱,核对恢复路径的费用。负边为什么没有破坏这次计算?
  2. 执行。 对同一递推做一次按需记忆化,只请求 d[t],并按所列弧的顺序枚举每个顶点的入弧。记录首次进入、完成、缓存命中的状态。与填满全表相比,少算哪些状态?把“实际求值次数”与“函数调用次数”分开计数。
  3. 迁移。 把“前驱值加一步成本”迁移到本页背包表:执行只含重量 2、价值 3 的一件物品、容量 4 的一维更新,分别报告正序和逆序结果,并解释哪次读取已经属于本轮。再说明只保存最后一行为什么不足以直接恢复物品方案。
  4. 边界。 先加入 c→a:0,再单独考虑把这条新弧改成 c→a:−1。分别判断是否有有限最短值、是否还能直接拓扑填表。若改问一般有环图的最长简单路径,只记终点为什么不够?写出至少还须保留的一项历史信息。

验算标尺:全表按 s,a,b,c,t,x,y 排列为 (0,2,1,2,4,7,8),目标路径为 s→a→b→c→t。按需版本首次求值五个状态,发出八次调用,其中三次命中已完成缓存,不访问 x,y。一件物品的正序错误得到 6,逆序得到 3。加入权 0 的回边后,圈 a→b→c→a 总权为 0,最短值仍有限,但依赖有环,普通记忆化会在写入结果前递归回来;权改为 −1 后,该圈总权为负,且可到达 t,目标值为 −∞。可用Bellman–Ford把允许弧数加进状态求有限层答案并检测负圈,不能把回边随手删掉。最长简单路径则必须区分已访问顶点集合,这正是子集状态可能指数增长的原因。

参考资料
  • MIT 6.006,Lecture 16: Dynamic Programming Subproblems,2020,课程讲义:状态定义、递推关系、求值顺序与解重建。

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022,Part IV, Ch. 14 “Dynamic Programming”。

  • Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005,Ch. 6, dynamic programming and optimal substructure。

关系图谱41 个相邻概念 · 5 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
分类位置

上位 / 更一般

暂未标注直接上位概念。

下位 / 直接特例

类型化关系