动态规划

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

动态规划主动识别并合并相同子问题，以状态表或记忆化避免重复计算；回溯法公理库回溯法Backtracking深度优先枚举部分解并在不可能完成时撤销选择的搜索范式。沿选择树枚举候选，并靠可行性或界限剪枝撤销选择。两者可以组合，但“存在递归分支”并不足以构成动态规划。

Fibonacci 递归的调用树重复解同一下标，记忆化后只剩 $O(n)$ 个状态。最长公共子序列用两个前缀长度 $(i,j)$ 作状态，因而有 $(m+1)(n+1)$ 个前缀状态。0–1 背包可定义 $dp[i,w]$ 为前 $i$ 件物品在容量 $w$ 下的最大价值。设第 $i$ 件重量为 $a_i$、价值为 $v_i$，当 $w\ge a_i$ 时，转移为 $dp[i,w]=max\{dp[i-1,w],dp[i-1,w-a_i]+v_i\}$；第一项是不选，第二项是选一次，两者都只能读取上一行。

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

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

编辑距离网格公理库编辑距离的网格动态规划Levenshtein distance dynamic programming · Wagner–Fischer algorithm把插入、删除与替换写成前缀网格的三类边，求出最小改写费用并重建逐条可执行的脚本。把这一区别具体化：完整前缀表能回溯插删替换脚本，滚动行只保留费用。Hirschberg 方法公理库Hirschberg 线性空间序列比对Hirschberg algorithm · Linear-space sequence alignment用前向与反向滚动行认证最优路径的中线穿越点，释放分数数组后递归重建完整对齐。先用前后向费用认证中线切口，再释放数组、递归重建；因此要分别核算工作数组、递归栈和输出。

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

记忆化公理库记忆化Memoization缓存递归子问题结果以避免重复计算的自顶向下动态规划技术。以需求驱动方式解状态，表格法则按依赖顺序主动求值。动态规划可用于 DAG公理库有向无环图Directed acyclic graph · DAG不含有向环的有向图。 最短路、序列比对、背包、矩阵链乘、区间问题、树分解、概率模型与有限时域控制。其中计数、概率与可达性例子也说明，动态规划的主体是状态方程的有效求值，而不是优化问题所特有的“最优子结构”。它与分治的分界是是否复用重叠状态，与贪心的分界则是是否保留多种中间可能后再比较。

高级 DP 仍应从状态 DAG 看待，而不是把新技巧当模板名。子集动态规划公理库子集动态规划Subset dynamic programming以所有子集为状态执行精确指数动态规划，并准确计算转移枚举量。把 $2^n$ 个子集作为节点，树宽 DP公理库树宽上的动态规划treewidth dynamic programming · DP on tree decompositions以最大独立集的完整逐袋计算，证明树分解边界状态、合并去重与回溯，并区分宽度、袋数和分解成本。把 bag 边界状态沿树分解传播，Color Coding公理库Color Codingcolor-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把候选转移改写成直线，在斜率与查询点都单调时用双端队列维护下包络，并以交点顺序证明删线安全。利用斜率与查询顺序维护候选。每一种省略都要对应自己的结构证明。