从四件物品开始
容量只有 7 的背包,面前有四件各只能取一次的物品:A 的重量、价值为 ( 1 , 1 ) ,B 为 ( 3 , 4 ) ,C 为 ( 4 , 5 ) ,D 为 ( 5 , 7 ) 。按单位重量价值从高到低取,会先拿 D,再拿 A,得到 8 ;B 与 C 合起来却重 7 、值 9 。局部最划算的一件,可能挤掉更好的组合。
不妨先问一个更小、含义明确的问题:d p [ i , w ] 表示只用前 i 件、总重量不超过 w 的最大价值。对第 i 件,任何装法都只有不选、选一次两种情况:
d p [ i , w ] = { d p [ i − 1 , w ] , w < a i , max { d p [ i − 1 , w ] , d p [ i − 1 , w − a i ] + v i } , w ≥ a i . 没有物品时 d p [ 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 ) ) 位。这是伪多项式界,不能只见到二维表就认定算法对输入长度为多项式。
形式陈述
动态规划把序列递推 理路 递推关系 Recurrence relation 用先前项规定序列当前项的关系。 推广为状态集 S 上的方程:每个 s ∈ S 的值只由其直接依赖 pred ( s ) 的值组合而成,并为无依赖状态给出基例。若依赖关系是有限无环图,就用拓扑排序 理路 拓扑排序 Topological sort 给有向无环图顶点排列线性次序,使每条边从前指向后。 确定填表次序。这里画边 t → s 表示计算 s 要读 t 的值,即箭头由依赖项指向使用它的状态;求值按拓扑序前进,递归查找依赖则沿箭头反向展开。拓扑序可以直接由下标给出,不必另行建图、运行排序程序。
记忆化 理路 记忆化 Memoization 在有限无环、状态充分的递归中缓存已完成结果,以需求驱动实现动态规划。 给出自顶向下的具体实现:从目标递归求依赖,完成一个状态就缓存结果。本页的实现保证以状态键包含全部相关输入、结果确定、可达依赖有限无环、各局部计算终止、缓存不淘汰为条件;满足这些条件时,它与同一基例和递推的拓扑填表在共同计算的状态上给出相同值。这不承诺相同的访问集合、栈深、内存布局或成本,也不把任意函数缓存都当作动态规划。更一般地,依赖可以由严格关系 ≺ 给出:若 t ∈ pred ( s ) 时总有 t ≺ s ,且 ≺ 是良基的,则可用良基递归确定每个状态值。要得到有限算法,还需目标可达的依赖图有限,每个状态的直接依赖可有效枚举,基例与组合运算能在有限时间完成。良基性本身允许无限多个直接依赖,不能替代这些计算条件。
优化问题常有
F ( s ) = opt a ∈ 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 ) ;还需为所用迭代证明收敛到该不动点。任意环状递推方程不会因为“可以反复更新”就自动成为动态规划:解可能不存在、不唯一,或更新根本不收敛。
直觉
动态规划先问“未来究竟需要哪些过去信息”,再把这份充分摘要定义为状态。当两条路径得到同一状态时,它们的后续计算便可合并。状态太少会丢失影响未来的信息,太多则把整段历史原样带入。因此核心工作是证明状态充分、转移完备,并给出合法求值顺序。
图片加载失败 动态规划状态依赖与填表顺序
例子与边界
动态规划主动识别并合并相同子问题,以状态表或记忆化避免重复计算;回溯法 理路 回溯法 Backtracking 深度优先枚举部分解并在不可能完成时撤销选择的搜索范式。 沿选择树枚举候选,并靠可行性或界限剪枝撤销选择。两者可以组合,但“存在递归分支”并不足以构成动态规划。
背包递推的两个分支都只读上一行,因此可以压成一行;但省去一个下标以后,旧值与新值会共用地址,执行顺序就成了正确性的一部分。
只考虑一件重量 2 、价值 3 的物品,容量为 4 ,初始一维表全零。若容量从小到大更新,先把 d p [ 2 ] 设为 3 ,再用这个刚写入的值计算 d p [ 4 ] = d p [ 2 ] + 3 = 6 ,相当于把物品选了两次。从大到小更新时,计算 d p [ 4 ] 读到的 d p [ 2 ] 仍是上一行的 0 ,结果为 3 ;之后才改 d p [ 2 ] 。逆序不是口诀,而是在原地存储中保留递推依赖的旧版本。
若还要输出选中的物品,仅存最优数值不够;可在二维表记录每个状态采用哪条转移,再从目标状态沿选择倒推。压缩空间后这些历史选择可能被覆盖,需要另存信息或重新计算,不能把数值计算的空间界直接当成完整解重建的空间界。
编辑距离网格 理路 编辑距离的网格动态规划 Levenshtein distance dynamic programming · Wagner–Fischer algorithm 把插入、删除与替换写成前缀网格的三类边,求出最小改写费用并重建逐条可执行的脚本。 把这一区别具体化:完整前缀表能回溯插删替换脚本,滚动行只保留费用。Hirschberg 方法 理路 Hirschberg 线性空间序列比对 Hirschberg algorithm · Linear-space sequence alignment 用前向与反向滚动行认证最优路径的中线穿越点,释放分数数组后递归重建完整对齐。 先用前后向费用认证中线切口,再释放数组、递归重建;因此要分别核算工作数组、递归栈和输出。
状态设为“当前价值”却不保留已用容量,通常无法决定背包的后续可行性;反过来,把所有已选集合当作状态虽然充分,却退化为指数枚举。“写出了递推式”只是起点;还必须证明状态确实包含后续所需的全部信息,转移覆盖了所有合法情形,且所选求值规则真能得到指定的解。
最少回文分解 理路 最少回文分解动态规划 Minimum palindromic factorization · Palindromic length · 最小回文切分 以已覆盖的前缀长度为状态,枚举全部非空回文末块,计算最少块数并重建切点,区分线性回文预处理与二次方转移成本。 给出一个完整的前缀状态实例:枚举所有回文末块,再由前驱表输出真实切点。aaba 否定先取最长回文前缀的贪心;线性时间求好回文半径后,候选切点总数仍可能是二次方,因而预处理变快不等于整个DP变快。
推论与应用
记忆化 理路 记忆化 Memoization 在有限无环、状态充分的递归中缓存已完成结果,以需求驱动实现动态规划。 以需求驱动方式解状态,表格法则按依赖顺序主动求值。动态规划可用于 DAG 理路 有向无环图 Directed acyclic graph · DAG 不含有向环的有向图。 最短路、序列比对、背包、矩阵链乘、区间问题、树分解、概率模型与有限时域控制。其中计数、概率与可达性例子也说明,动态规划的主体是状态方程的有效求值,而不是优化问题所特有的“最优子结构”。与分治 理路 分治法 Divide and conquer 把问题分成较小同类子问题,递归求解后合并结果的算法设计范式。 比较时,应看是否主动合并相同子问题,而不是只看有没有递归:归并排序的两半可以各算各的,Fibonacci 的重复下标则值得缓存。分治也能与动态规划组合,Hirschberg 重建就是例子;两种范式不是互斥分类。与贪心 理路 贪心算法 Greedy algorithm 每一步作局部最优且不回溯选择的算法设计范式。 比较时,开头的背包反例说明:只保留一个局部选择需要安全选择证明,不能用“看起来最划算”替代对其余状态的比较。
高级 DP 仍应从状态 DAG 看待,而不是把新技巧当模板名。子集动态规划 理路 子集动态规划 Subset dynamic programming 以所有子集为状态执行精确指数动态规划,并准确计算转移枚举量。 把 2 n 个子集作为节点,树宽 DP 理路 树宽上的动态规划 treewidth dynamic programming · DP on tree decompositions 以最大独立集的完整逐袋计算,证明树分解边界状态、合并去重与回溯,并区分宽度、袋数和分解成本。 把 bag 边界状态沿树分解传播,Color Coding 理路 Color Coding color-coding · 颜色编码法 随机把顶点染成 k 色,将简单子图的顶点互异约束转成颜色子集动态规划。 用随机着色压缩“互异顶点”约束;三者分别以指数状态、结构参数和随机化换可解性。四俄罗斯与字级并行 理路 四俄罗斯方法与字级并行 Four Russians method · bit parallelism · broadword programming 把状态切成可查表微块,或在一个机器字内并行处理多位,从而省去对数因子。 则批量执行一组有限转移,只改善每条边的处理成本,不改变状态依赖正确性。
另一些加速减少的是候选转移。Monge 四点不等式 理路 Monge 数组与交叉交换不等式 Monge array · Monge matrix 用任意四个有序格子的交换不等式控制行极小值的位置,并把平方分段费用转化成可证明的候选单调性。 可证明最左切点单调,分治 DP 优化 理路 决策单调的分治 DP 优化 Divide-and-conquer DP optimization 在已证明最优切点单调的分层递推中,先求中间状态,再用它收紧左右候选区间,逐层安全省去转移。 再据此收紧搜索范围;若转移还能展开为直线查询,直线下包络 理路 单调直线下包络优化 Monotone convex hull trick · Monotone line container 把候选转移改写成直线,在斜率与查询点都单调时用双端队列维护下包络,并以交点顺序证明删线安全。 利用斜率与查询顺序维护候选。每一种省略都要对应自己的结构证明。
固定位费用LZ77解析 理路 固定位费用的LZ77最优解析 Fixed-cost LZ77 parsing · Gamma-cost LZ77 parsing · 固定位码制的最优回指解析 固定字面量与gamma长度距离码的逐token位费用,以距离价格带和长度价格区间压缩完整转移,求可重建且可解码的最小payload。 提供另一种完整转移压缩:同一距离价格档先求最长可复制前缀,再把相同长度费用的一段目的位置交给区间最小值。每个合法长度仍被某个区间覆盖,所省的是枚举工作而不是未经证明地丢弃选择;只有码价不随此前解析改变时,单独记当前位置才足以决定剩余问题。
单元终结任务:把一张依赖图算成答案
给定顶点 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 ”的依赖弧。请交付下面四项,而不只写最终数字:
计算。 给出一个拓扑序,列出全部七个状态值和取最小值的前驱。从 t 倒走前驱,核对恢复路径的费用。负边为什么没有破坏这次计算?
执行。 对同一递推做一次按需记忆化,只请求 d [ t ] ,并按所列弧的顺序枚举每个顶点的入弧。记录首次进入、完成、缓存命中的状态。与填满全表相比,少算哪些状态?把“实际求值次数”与“函数调用次数”分开计数。
迁移。 把“前驱值加一步成本”迁移到本页背包表:执行只含重量 2 、价值 3 的一件物品、容量 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 理路 Bellman–Ford 算法 Bellman–Ford algorithm 通过反复松弛边求含负权边图的单源最短路并检测可达负环。 把允许弧数加进状态求有限层答案并检测负圈,不能把回边随手删掉。最长简单路径则必须区分已访问顶点集合,这正是子集状态可能指数增长的原因。
参考资料
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。