算法设计第 3 章：动态规划——状态、转移方程与填表顺序
动态规划是全课程的分水岭，也是最多人"看得懂答案、写不出方程"的一章。它不难在代码，难在把问题定义成一个可递推的状态：状态选对了，转移方程几乎是自然语言直译；状态选错了，怎么调都是错的。这一章的主线只有一条——先证最优子结构，再定状态与转移，最后决定填表方向。学完应当能独立推导矩阵连乘与 0-1 背包的方程，并说清备忘录与自底向上的取舍。
一、两个前提：最优子结构与重叠子问题
最优子结构：问题的最优解包含其子问题的最优解。矩阵连乘中，若 A[i..j] 的最优完全加括号在 k 处断开，则 A[i..k] 与 A[k+1..j] 也必须各自最优——否则替换成更优的切法就能改进原解，矛盾。
重叠子问题：递归分解出的子问题大量重复。矩阵连乘的朴素递归要算 Ω(2ⁿ) 次子问题，而不同的子问题只有 O(n²) 个。重叠是动态规划存在的理由：分治的子问题互不相交，动态规划的子问题成片重合。
两个条件缺一不可。只有最优子结构没有重叠（如归并排序），用分治即可；有重叠但最优解不能由子问题最优解拼出（如最长简单路径），动态规划失效。
还有一条常被忽略的前提是无后效性：一旦状态确定，后续决策只依赖状态本身，与到达该状态的路径无关。背包里体现为"前 i 件、容量 c"这一对值唯一决定剩余决策；若约束变成"选了 A 才能选 B"，一维容量就不够，必须把"已选集合"编进状态。状态定义得不对，转移方程再漂亮也是错的。
二、矩阵连乘：状态与转移方程的样板
问题：给定 n 个矩阵的维数序列 p₀, p₁, …, pₙ（Aᵢ 是 pᵢ₋₁ × pᵢ），求完全加括号使标量乘法次数最少。
状态：m[i][j] 表示计算 A[i..j] 所需的最少乘法次数。
转移方程：
m[i][j] = 0 , i == j
m[i][j] = min { m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j] } , i < j, i <= k < j
最后一项是"两个子链的结果矩阵相乘"的代价：(pᵢ₋₁ × pₖ) 乘 (pₖ × pⱼ)。这一项是整个方程的关键，漏掉它方程就退化成"找最短子链"，答案荒谬。
填表顺序：m[i][j] 依赖长度更短的区间，所以按区间长度 len = 2..n 递增填，j = i + len − 1。这就是"自底向上"的含义——保证用到的值已经算好。
复杂度：状态 O(n²) 个，每个状态枚举 k 有 O(n) 种，时间 O(n³)，空间 O(n²)。这个 O(n³) 是第 10 章四边形不等式优化的起点，可降到 O(n²)。
三、自底向上填表与备忘录方法
| 维度 | 自底向上（填表） | 自顶向下（备忘录） |
|---|---|---|
| 计算范围 | 全部 O(n²) 个状态 | 只算真正被用到的状态 |
| 递归开销 | 无 | 有函数调用开销 |
| 空间 | 可滚动优化 | 需保留递归栈 |
| 适用 | 状态稠密、几乎都要算 | 状态稀疏、很多用不上 |
备忘录是"带缓存的递归"：进入函数先查表，命中即返回，未命中则递归计算并写表。它把指数级递归压到多项式，但保留了递归的直观性。矩阵连乘的状态几乎全被用到，两者等价；某些树上 DP 只有少量状态可达，备忘录能省一个量级。
四、回溯构造具体最优方案
DP 只给出最优值，要输出"怎么切"需要记录决策：用 s[i][j] 记下取到最小值的那个 k。填完表后从 s[1][n] 出发递归展开：输出 (A[1..s])(A[s+1..n])，再对两段递归。回溯的代价是 O(n)，因为每层只做常数工作。
这条"值 + 决策"的双表结构是所有方案重构问题的通用套路：背包记"第 i 件是否放入"，LCS 记"从哪个方向转移来"，TSP 记"上一个城市"。
五、0-1 背包与流水作业调度
0-1 背包：n 件物品，第 i 件重 wᵢ、价值 vᵢ，容量 C。状态 f[i][c] 表示前 i 件在容量 c 下的最大价值：
f[i][c] = max( f[i-1][c], f[i-1][c-w[i]] + v[i] ) , c >= w[i]
f[i][c] = f[i-1][c] , c < w[i]
时间 O(nC)，空间 O(nC)。注意这是伪多项式算法：C 用二进制编码时输入规模是 log C，O(nC) 关于输入长度是指数的，这正是第 8 章背包问题是 NP 完全问题的原因。
完全背包只需把 c 的枚举方向从大到小改成从小到大，就允许同一件物品重复选——方向决定了"能不能再用一次"，这是个高频易错点。
流水作业调度（n 个作业在两台机器 M1、M2 上加工，次序相同，求最短总工期）：由 Johnson 法则，把作业分成 aᵢ ≤ bᵢ 与 aᵢ > bᵢ 两类，前者按 aᵢ 升序、后者按 bᵢ 降序拼接，O(n log n)。它本质是贪心，但也可写成 DP 验证，是本章与第 4 章的接缝。
六、滚动数组与四边形不等式入门
滚动数组：若 f[i][*] 只依赖 f[i-1][*]，可把第一维压成 2 行；0-1 背包更彻底——容量维从大到小枚举时，一维数组原地更新即可，空间从 O(nC) 降到 O(C)。逆序的原因是一维数组同时扮演"旧行"和"新行"，正序会让同一件物品被重复使用。
for (int i = 1; i <= n; i++)
for (int c = C; c >= w[i]; c--) /* 逆序：每件物品至多用一次 */
f[c] = max(f[c], f[c - w[i]] + v[i]);
这段五行代码里藏着两个考点：逆序保证 0-1 语义，c >= w[i] 保证不越界。把内层改成 c = w[i]; c <= C; c++ 就变成完全背包，把 max 换成计数就变成"装满容量的方案数"——同一个转移式，方向与初值一变，问题就换了一个。
状态设计的三问，写任何 DP 前都过一遍：状态是否唯一确定后续决策（无后效性）？状态是否足够表达约束（不少）？状态数是否可接受（不多）？三者冲突时优先保无后效性，必要时升维。
四边形不等式：若代价函数 w 满足 w(a,c) + w(b,d) ≤ w(a,d) + w(b,c)（a ≤ b ≤ c ≤ d，即"交叉优于嵌套"），则最优决策点 s[i][j] 满足单调性 s[i][j−1] ≤ s[i][j] ≤ s[i+1][j]。于是枚举 k 的范围从 O(n) 缩到均摊 O(1)，区间 DP 从 O(n³) 降到 O(n²)。这是第 10 章的重点，此处只需记住判据与结论。
易错点
- 矩阵连乘漏掉 pᵢ₋₁·pₖ·pⱼ 这一项，或把下标写成 pᵢ·pₖ·pⱼ。
- 填表顺序与依赖方向不一致，用到未初始化的值。
- 0-1 背包用一维数组时正序枚举容量，退化成完全背包。
- 把 O(nC) 当作多项式时间，误判背包属于 P 类。
- 只求最优值不记决策表，最后无法输出方案。
这一章在整门课里的位置
本章直接建立在第 2 章的递归与分治之上：动态规划就是把分治里重叠的那部分子问题缓存起来。它的"状态—转移—填表"三段式会被第 6 章的分支限界（用 DP 估界）、第 8 章的近似算法（用 DP 求松弛问题）、第 9 章的编辑距离与 LCS 反复调用，第 10 章的四边形不等式则是本章 O(n³) 的直接优化。
本文是《算法设计与分析（89 讲）》第 3 章的知识点摘要。完整板书与代码见 课程页；上一章 递归与分治，下一章 贪心算法。
相关课程
这篇笔记涉及的主题，我录过对应的视频课程：
- 算法设计与分析（89讲） 89 讲