第 15 章动态规划 (Dynamic Programming)

核心结论

动态规划 (DP)：适用于「最优子结构 + 重叠子问题」的优化问题；分四步：(1) 刻画最优解结构；(2) 递归定义最优解的值；(3) 自底向上计算最优解；(4) 构造最优解（若需）。
钢条切割 (Rod Cutting)：rn = max_{1≤i≤n} (pi + r_{n-i})；朴素递归 2^n，DP 底向上 O(n²)；记忆化递归同 O(n²)。
矩阵链乘 (Matrix-Chain Multiplication)：m[i,j] = min_{i≤k<j} {m[i,k] + m[k+1,j] + p_{i-1} p_k p_j}；O(n³) 时间 + O(n²) 空间，s[i,j] 表存最优分割点。
最长公共子序列 (LCS)：c[i,j] 是 Xi 与 Yj 的 LCS 长度；若 xi = yj 则 c[i-1,j-1]+1；否则 max(c[i-1,j], c[i,j-1])；O(mn) 时间。
最优二叉搜索树 (Optimal BST)：e[i,j] 是含 ki..kj 的最优 BST 期望搜索代价；min_{i≤r≤j} {e[i,r-1] + e[r+1,j] + w(i,j)}；Θ(n³) 时间。
DP 适用条件：(a) 最优子结构（cut-and-paste 论证）；(b) 重叠子问题（总不同子问题数多项式）；(c) 子问题独立（资源不冲突）。

本章主旨

本章是「算法设计范式」的第二章——分治之后是动态规划。DP 与分治的关键区别在于「子问题是否重叠」：分治（合并排序）的子问题 disjoint，每次产生新子问题；DP（钢条切割、矩阵链乘、LCS、最优 BST）的子问题 overlap，需要「存储子问题解以避免重复计算」。本章通过四个经典例子（§15.1-15.5）展示 DP 的设计流程，§15.3 抽象出 DP 适用条件（最优子结构 + 重叠子问题 + 子问题独立），并讨论三种实现（自底向上表格、记忆化递归、半记忆化）。DP 是「时间-空间权衡」的典型——用额外空间换时间，从指数降到多项式。

一、核心概念

本章围绕 5 个核心概念展开：从钢条切割（最简 DP）开始，扩展到矩阵链乘（区间子问题）、LCS（双序列子问题），再用 DP 一般适用条件抽象经验，最后用最优 BST 演示「概率权重的 DP」。

概念	定义 + 重要性	实现提示
动态规划 4 步法	(1) 刻画最优解结构（最优子结构）；(2) 递归定义最优解的值（带基础情形）；(3) 自底向上 DP 或自顶向下记忆化计算；(4) 回溯构造最优解。	§15 引言；DP 是「时间-空间 trade-off」——额外表格存储换时间，从指数变多项式。
钢条切割 (Rod Cutting)	切割价格表 pi 求 rn 最大；递推 rn = max_{1≤i≤n} (pi + r_{n-i})；朴素递归 Θ(2^n) → DP Θ(n²)；附 EXTENDED-BOTTOM-UP-CUT-ROD 记录 s[n] 回溯切割方案。	§15.1；CUT-ROD 朴素版 2^n 次调用；BOTTOM-UP-CUT-ROD 双重循环 O(n²)；子问题图 DAG。
矩阵链乘最优加括号	n 个矩阵连乘求最小标量乘次数；m[i,j] = min_{i≤k<j} (m[i,k] + m[k+1,j] + p_{i-1} pk pj)；O(n³) 时间和 Θ(n²) 空间；s[i,j] 记录最优 k；PRINT-OPTIMAL-PARENS 回溯输出括号。	§15.2；Catalan 数 P(n) = Ω(4^n/n{3/2}) 种加括号；DP 极大加速；区间子问题。
LCS (Longest Common Subsequence)	两序列 X[1..m]、Y[1..n] 的最长公共子序列；c[i,j] 长度 + 定理 15.1 三种情形；若 xi = yj 则 c[i-1,j-1]+1；否则 max(c[i-1,j], c[i,j-1])；Θ(mn) 时间 + 空间。	§15.4；LCS-LENGTH + PRINT-LCS；只存上两行可省空间——若只求长度，可用 Hirschberg 二分技巧 O(m+n) 空间。
DP 适用条件 (Optimal Substructure + Overlapping Subproblems)	三大要素：(a) 最优子结构——cut-and-paste 证；(b) 子问题数量多项式；(c) 子问题独立（资源不共享）；反例：最长简单路径无最优子结构。	§15.3；与分治对比：DP 是「自顶向下递归 + 缓存」或「自底向上表格」；分治是「独立的子问题 → 递归树」。

概念

定义 + 重要性

实现提示

动态规划 4 步法

(1) 刻画最优解结构（最优子结构）；(2) 递归定义最优解的值（带基础情形）；(3) 自底向上 DP 或自顶向下记忆化计算；(4) 回溯构造最优解。

§15 引言；DP 是「时间-空间 trade-off」——额外表格存储换时间，从指数变多项式。

钢条切割 (Rod Cutting)

切割价格表 pi 求 rn 最大；递推 rn = max_{1≤i≤n} (pi + r_{n-i})；朴素递归 Θ(2^n) → DP Θ(n²)；附 EXTENDED-BOTTOM-UP-CUT-ROD 记录 s[n] 回溯切割方案。

§15.1；CUT-ROD 朴素版 2^n 次调用；BOTTOM-UP-CUT-ROD 双重循环 O(n²)；子问题图 DAG。

矩阵链乘最优加括号

n 个矩阵连乘求最小标量乘次数；m[i,j] = min_{i≤k<j} (m[i,k] + m[k+1,j] + p_{i-1} pk pj)；O(n³) 时间和 Θ(n²) 空间；s[i,j] 记录最优 k；PRINT-OPTIMAL-PARENS 回溯输出括号。

§15.2；Catalan 数 P(n) = Ω(4^n/n{3/2}) 种加括号；DP 极大加速；区间子问题。

LCS (Longest Common Subsequence)

两序列 X[1..m]、Y[1..n] 的最长公共子序列；c[i,j] 长度 + 定理 15.1 三种情形；若 xi = yj 则 c[i-1,j-1]+1；否则 max(c[i-1,j], c[i,j-1])；Θ(mn) 时间 + 空间。

§15.4；LCS-LENGTH + PRINT-LCS；只存上两行可省空间——若只求长度，可用 Hirschberg 二分技巧 O(m+n) 空间。

DP 适用条件 (Optimal Substructure + Overlapping Subproblems)

三大要素：(a) 最优子结构——cut-and-paste 证；(b) 子问题数量多项式；(c) 子问题独立（资源不共享）；反例：最长简单路径无最优子结构。

§15.3；与分治对比：DP 是「自顶向下递归 + 缓存」或「自底向上表格」；分治是「独立的子问题 → 递归树」。

二、详细笔记

15.1 钢条切割 (Rod Cutting)

What：给定长度 n 的钢条和价格表 pi（i = 1..n），求切割方案使收入 rn 最大。

Why：最简 DP 例子——清晰展示「朴素递归指数 vs DP 多项式」的对比，引出 DP 的核心思想：存储子问题解。

How：

递推（式 15.2）：

\[r_n = \max_{1 \le i \le n} (p_i + r_{n-i}) \quad \text{(r}_0 = 0)\]
朴素 CUT-ROD：

\[\begin{array}{rl} & \textbf{CUT-ROD}(p, n) \\ 1 & \textbf{if } n == 0 \textbf{ return } 0 \\ 2 & q = -\infty \\ 3 & \textbf{for } i = 1 \textbf{ to } n \\ 4 & \quad q = \max(q, p[i] + \textbf{CUT-ROD}(p, n-i)) \\ 5 & \textbf{return } q \end{array}\]

朴素递归调用次数 T(n) = 2^n——指数时间（式 15.4）。
BOTTOM-UP-CUT-ROD：

\[\begin{array}{rl} & \textbf{BOTTOM-UP-CUT-ROD}(p, n) \\ 1 & \textbf{let } r[0..n] \textbf{ be new array} \\ 2 & r[0] = 0 \\ 3 & \textbf{for } j = 1 \textbf{ to } n \\ 4 & \quad q = -\infty \\ 5 & \quad \textbf{for } i = 1 \textbf{ to } j \\ 6 & \quad\quad q = \max(q, p[i] + r[j-i]) \\ 7 & \quad r[j] = q \\ 8 & \textbf{return } r[n] \end{array}\]

双重循环 → Θ(n²) 时间；r[n] 是最优收入。
回溯构造切割方案：EXTENDED-BOTTOM-UP-CUT-ROD 额外存 s[j] = 最优首段长度；PRINT-CUT-ROD-SOLUTION 沿 s[] 输出切割序列。
子问题图 (Subproblem Graph)：钢条切割 DAG——n 顶点（大小 0 到 n-1），每顶点度 ≤ n；DP 时间 = 顶点数 + 边数。

When： . 实际中可用贪心（按 pi/i 选最大密度）但不一定最优（练习 15.1-2 反例）。 . 朴素递归 = 计数问题本身的复杂度（本题 2^n 种切割）；DP 显著加速。 . 切割成本 c 附加（练习 15.1-3）→ 加 c 于递归式。

Example（n = 4，价格表 [1, 5, 8, 9]）： * r[1] = 1（不切） * r[2] = max(p[2], p[1]+r[1]) = max(5, 1+1) = 5 * r[3] = max(p[3]=8, p[1]+r[2]=6, p[2]+r[1]=6) = 8 * r[4] = max(p[4]=9, p[1]+r[3]=9, p[2]+r[2]=10, p[3]+r[1]=9) = 10（切割 2+2）

15.2 矩阵链乘 (Matrix-Chain Multiplication)

What：n 个矩阵相乘求最小标量乘法次数的加括号方案。

Why：经典 DP — 区间型子问题 + 多子问题；展示「乘法次数可差 10 倍以上」（同样三个矩阵，不同括号差 7500 vs 75000 标量乘）。

How：

递推（式 15.7）：

\[m[i,j] = \begin{cases} 0 & \text{if } i = j \\ \min_{i \le k < j} \{m[i,k] + m[k+1,j] + p_{i-1} p_k p_j\} & \text{if } i < j \end{cases}\]
MATRIX-CHAIN-ORDER（自底向上）：按链长 l 从 2 到 n 递推；对每个 i, j = i+l-1，遍历 k ∈ [i, j-1]。
复杂度：三层循环（l / i / k 各 ≤ n） → O(n³)；表 m 和 s 各 Θ(n²) 空间。
PRINT-OPTIMAL-PARENS 回溯：根据 s[i,j] 递归打括号，O(n) 时间。
子问题图：Θ(n²) 顶点；每顶点度 ≤ n-1 → 总边 O(n³)。

When： . 计算代价昂贵的矩阵乘法（如深度学习）→ 必须最优加括号。 . 矩阵固定不变 → 提前计算 s[] 重复使用。 . 实际可用 Hu-Shing O(n lg n) 算法（章节备注提到）。

Example（链长 6，p = [30, 35, 15, 5, 10, 20, 25]）： * 最优 m[1,6] = 15,125（s[1,6] = 3 → (A1 A2 A3)(A4 A5 A6)）。 * 若不优化（标准 (A1(…An))）可能需 75,000+ 次乘法。

15.3 动态规划要素

What：抽象出 DP 适用的两大要素：「最优子结构」和「重叠子问题」。

Why：避免对每个问题都重新设计——先检验是否满足两大要素。

How：

最优子结构：
- 问题的一个最优解包含其子问题的最优解。
- 证明模式（cut-and-paste）：假设子问题解不是最优 → 替换后整体更优 → 矛盾。
- 子问题数量与选择数决定 DP 时间：T(DP) = (#subproblems) × (#choices per subproblem)。
重叠子问题：
- 递归算法反复求解相同子问题（区别于分治的「总是新子问题」）。
- 子问题总数 = 多项式（在输入规模上）。
反例：最长简单路径：
- 不满足最优子结构：q → r → t 是 q 到 t 最长，但子路径 q → r、r → t 都不是最长。
- 子问题资源（顶点）共享 → 子问题间不独立。
- 问题属于 NP-complete。
子问题独立：
- 与「重叠」并不矛盾——独立指资源不共享；重叠指同样子问题多次出现。
记忆化 (Memoization)：
- 自顶向下递归 + 表格缓存。
- 第一次访问子问题：计算并存表；后续访问：O(1) 查表。
- 与「自底向上表格」时间同阶（Θ 等级），常数略大（递归调用开销）。

When： . 问题有最优子结构 + 重叠子问题 + 子问题独立 → DP 可用。 . 「最长」相关问题（最长路径、最长简单路径） → 多半不满足最优子结构。 . 决策路径不确定 → 通常是 DP（如选择哪种切法 / 加括号）。

Example（剪贴论证）： * 假设矩阵链最优加括号在 Ak 分割 → 子链 Ai..Ak 和 A_{k+1}..Aj 必各自最优。 * 反证：若 Ai..Ak 有更优加括号 L' → 用 L' 替换，整体代价降低 → 矛盾。

15.4 最长公共子序列 (LCS)

What：两序列 X[1..m]、Y[1..n] 的最长公共子序列（保持顺序可跳跃）。

Why：DNA 比对、版本控制、diff 工具的核心算法；展示「条件转移」型 DP（不同情形不同子问题）。

How：

递推（式 15.9，定理 15.1）：

\[c[i,j] = \begin{cases} 0 & \text{if } i = 0 \text{ or } j = 0 \\ c[i-1,j-1] + 1 & \text{if } x_i = y_j \\ \max(c[i-1,j], c[i,j-1]) & \text{if } x_i \neq y_j \end{cases}\]
LCS-LENGTH（自底向上）：m × n 表按行填；b[i,j] 存方向（↖/↑/←）；c[m,n] 是 LCS 长度。
PRINT-LCS：从 b[m,n] 沿箭头回溯，遇 ↖ 输出 xi；O(m+n) 时间。
复杂度：Θ(mn) 时间 + Θ(mn) 空间（表 c 和 b）。
改进：
- 省 b 表 → Θ(m+n) 重建（练习 15.4-2）。
- 只存 2 行 c → 空间 O(min(m,n))（仅求长度）。
- Hirschberg 算法 → O(m+n) 空间 + Θ(mn) 时间（结合行存和二分）。

When： . DNA / 字符串比对、文件 diff、文本相似度 → LCS（或其变种如编辑距离）。 . 处理所有 α ∈ Σ（字符表大小有界）→ 可用 Four Russians / hashing 加速。

Example（X = ⟨A, B, C, B, D, A, B⟩，Y = ⟨B, D, C, A, B, A⟩）： * c 表对应 LCS = BCBA，长度 4（图 15.8）。

15.5 最优二叉搜索树 (Optimal BST)

What：已知搜索概率 pi（键）和 qi（不在键之间的区间），构造期望搜索代价最小的 BST。

Why：把搜索树做得「加权平衡」——常搜的键放近根；与第 13 章红黑树（几何平衡，权重无差别）形成对照。

How：

期望代价定义（式 15.11）：

\[E[\text{search cost in } T] = \sum_{i=1}^{n} (\text{depth}_T(k_i) + 1) p_i + \sum_{i=0}^{n} (\text{depth}_T(d_i) + 1) q_i\]
递推（式 15.14）：

\[e[i,j] = \begin{cases} q_{i-1} & \text{if } j = i-1 \\ \min_{i \le r \le j} \{e[i,r-1] + e[r+1,j] + w(i,j)\} & \text{otherwise} \end{cases}\]

其中 w(i,j) = 子树权重和（式 15.12），根选 r 时代价增 w(i,j)。
OPTIMAL-BST：三循环（l / i / r），计算 e 表 + root 表；Θ(n³) 时间 + Θ(n²) 空间。
改进（练习 15.5-4）：Knuth 证明 root[i,j-1] ≤ root[i,j] ≤ root[i+1,j] → 限制 r 扫描范围 → Θ(n²) 时间。

When： . 静态键集 + 已知搜索频率 → 最优 BST（编译器的关键字表）。 . 动态键集或动态频率 → 跳表 / 自调整树（Splay）。 . 简化为「平均深度最小」→ 平衡 BST（红黑树）即可——不优化权重。

Example（图 15.9-15.10，n = 5 键，p = [0.15, 0.10, 0.05, 0.10, 0.20]，q = [0.05, 0.10, 0.05, 0.05, 0.05, 0.10]）： * 最优 BST 期望代价 2.75（不是「最高概率键放根」——因为高概率键 k5 放根时代价 2.85）。

三、关键图表

核心公式对照表

式编号

内容

式 15.1

钢条切割递推：rn = max(pn, r1+r_{n-1}, …, r_{n-1}+r1)

式 15.2

简化：rn = max_{1≤i≤n} (pi + r_{n-i})

式 15.4

朴素 CUT-ROD 复杂度：T(n) = 2^n

钢条切割 DP

O(n²) 时间

式 15.6

矩阵链加括号数 P(n) 递推 = Catalan 数，Ω(4^n/n{3/2})

式 15.7

矩阵链乘递推 m[i,j]

矩阵链乘 DP

O(n³) 时间 + O(n²) 空间

式 15.9

LCS 递推 c[i,j]

LCS-LENGTH

Θ(mn) 时间 + 空间

定理 15.1

LCS 三种情形：xi=yj / Z 不含 xm / Z 不含 yn

式 15.11

最优 BST 期望搜索代价

式 15.12

w(i,j) = 子树权重和

式 15.13

e[i,j] = e[i,r-1] + e[r+1,j] + w(i,j)

式 15.14

最优 BST 递推：min over r

最优 BST DP

Θ(n³) 时间 + O(n²) 空间（改进后 Θ(n²)）

不可 DP 反例

无权最长简单路径——子问题不独立

不可 DP 反例 2

钢条切割带限制 li——失去最优子结构

四、思维导图

mindmap
  root((第 15 章 动态规划))
    四步法
      最优结构
      递归定义
      自底向上
      构造解
    钢条切割
      rn=pi+rn-i
      O(n²)
      s[j]回溯
    矩阵链乘
      m[i,j]
      O(n³)
      区间子问题
    LCS
      c[i,j]
      Θ(mn)
      字符比对
    最优BST
      e[i,j]
      Θ(n³)
      概率加权
    适用条件
      最优子结构
      重叠
      独立
    反例
      最长路径
      限制切割
    实现
      自底向上
      记忆化
      回溯

五、重点与易错点

DP vs 分治：DP 子问题 overlap（共享）→ 需缓存；分治子问题 disjoint（独立）→ 不缓存。
DP vs 贪心：DP 求「所有子问题的最优解」后做选择；贪心「当下做局部最优选择」→ 各解一个子问题，效率高但适用范围窄（第 16 章）。
最优子结构证明 = cut-and-paste：假设子问题非最优，替换得到整体更优，矛盾。
子问题图 (Subproblem Graph) 是分析 DP 的关键工具——时间 = 顶点数 × 度数。
钢条切割朴素递归 = 2^n（式 15.4），但钢条只有 2^{n-1} 种切割；DP 表格只算 n 个不同大小子问题——指数到多项式。
矩阵链乘「n³ / n² 空间」 是经典结果——大部分「区间型 DP」都是 n³/n²；少数用单调性优化到 n²。
- 矩阵链乘数据规模：n = 100 时朴素枚举 4^100/n{3/2} 不可行；DP 1,000,000 次标量乘计算即可。
LCS 是条件转移型 DP——xi=yj 与否决定子问题不同；与钢条 / 矩阵链「无条件 split」不同。
LCS 不要求连续——子序列可跳跃；最长公共子数组（连续）= LCS 的特例，可用更高效的 KMP 变种。
LCS 不可作 LCS 的 LCS（错）——LCS 是「长度」而非「具体子序列」；两个 LCS 可能完全不同。
最优 BST 不一定「高概率键放根」——图 15.9 反例：k5 概率最高但放根时代价 2.85 > k2 放根的 2.75。
root[i,j-1] ≤ root[i,j] ≤ root[i+1,j]（Knuth 单调性）——可优化 e 循环到 O(n²)。
w(i,j) 不直接用式 15.12 计算——每次 O(j-i) 太慢；用表维护式 15.15：w[i,j] = w[i,j-1] + pj + qj → O(1)。
「半记忆化」：只对高代价子问题记忆化——节省存储但不损失太多速度（实践中不常见）。
- 动态规划 vs Memoization 内存上自底向上常胜——无递归开销、连续存储。
回溯信息 s[ ] / b[ ] / root[ ] 必须保存——否则重建解是多项式时间；省空间仅在不需要重建时（如 LCS-LENGTH 只求长度）。
- 「独立子问题」与「重叠子问题」不矛盾 — 独立指资源不共享，重叠指子问题出现多次，二者描述不同维度。
不能用 DP 的常见问题：(a) 无最优子结构（最长简单路径）；(b) 子问题不独立；(c) 子问题数指数（DP 退化为穷举）。

补充：与其他章节的衔接

第 4 章（分治策略）：DP 来自分治但解决「子问题 overlap」；与归并排序对比 = DP 不适用（独立子问题）。
第 16 章（贪心）：DP 是「穷尽所有子问题」后做选择；贪心是「每步局部最优 → 全局最优」。第 16 章用活动选择、Huffman 等展示贪心威力。
第 17 章（摊还分析）：某些 DP 问题用摊还视角分析（如「表占用摊还 O(1) / 操作」）。
第 22 章（DFS）/ 第 24-25 章（最短路径）：Floyd-Warshall 是 DP（顶点为阶段）；Bellman-Ford 可视为 DP（边数为阶段）。
第 32 章（字符串匹配）：编辑距离是 LCS 扩展（删除 / 插入 / 替换）；Levenshtein 距离用 DP 求解。
第 34 章（NP 完全性）：最长简单路径 NP-complete，证明 DP 不可能多项式时间解决；本章展示「何时 DP 可解」的判定。

第 15 章 动态规划 (Dynamic Programming)

核心结论

一、核心概念

二、详细笔记

15.1 钢条切割 (Rod Cutting)

15.2 矩阵链乘 (Matrix-Chain Multiplication)

15.3 动态规划要素

15.4 最长公共子序列 (LCS)

15.5 最优二叉搜索树 (Optimal BST)

三、关键图表

四、思维导图

五、重点与易错点

补充：与其他章节的衔接

第 15 章动态规划 (Dynamic Programming)