动态规划

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

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

Fibonacci 递归的调用树重复解同一下标，记忆化后只剩 $n$ 个状态。最长公共子序列用两个前缀长度 $(i,j)$ 作状态，因而有 $O(mn)$ 个子问题。0–1 背包可定义 $dp[i,w]$ 为前 $i$ 件物品在容量 $w$ 下的最大价值；压成一维后必须从大到小更新容量，否则本轮刚写入的值会让同一物品被重复选取。

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

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

高级 DP 仍应从状态 DAG 看待，而不是把新技巧当模板名。子集动态规划公理库子集动态规划Subset dynamic programming以所有子集为状态执行精确指数动态规划，并准确计算转移枚举量。把 $2^n$ 个子集作为节点，树宽 DP公理库树宽上的动态规划treewidth dynamic programming · DP on tree decompositions在 nice tree decomposition 的小 bag 边界上记录状态，以 f(k)n 时间求解近树图问题。把 bag 边界状态沿树分解传播，Color Coding公理库Color Codingcolor-coding · 颜色编码法随机把顶点染成 k 色，将简单子图的顶点互异约束转成颜色子集动态规划。用随机着色压缩“互异顶点”约束；三者分别以指数状态、结构参数和随机化换可解性。四俄罗斯与字级并行公理库四俄罗斯方法与字级并行Four Russians method · bit parallelism · broadword programming把状态切成可查表微块，或在一个机器字内并行处理多位，从而省去对数因子。则批量执行一组有限转移，只改善每条边的处理成本，不改变状态依赖正确性。