第14章 动态规划 — 章节汇总

章节概览

本章系统介绍了动态规划（Dynamic Programming）——一种通过最优子结构和重叠子问题两个关键性质，将指数级暴力搜索优化为多项式时间的算法设计范式。动态规划由 Richard Bellman 于1950年代提出，是算法设计中最重要的技术之一。本章通过5个经典问题（钢条切割、矩阵链乘法、LCS、最优BST）逐步展示DP的设计方法学。

---

14.1 钢条切割

小节	核心主题	关键结论
14.1 钢条切割	自顶向下（备忘录法）vs 自底向上	$\Theta (n^2)$

核心思路：将长度为 $n$ 的钢条切割问题分解为”第一次切割长度 $i$ + 剩余长度 $n-i$ 的最优解”，递归公式 $r_n={\max }_{1\le i\le n}(p_i+r_{n-i})$。

---

14.2 矩阵链乘法

小节	核心主题	关键结论
14.2 矩阵链乘法	区间DP、完全括号化	$\Theta (n^3)$

核心思路：对矩阵链 $⟨A_1,\dots ,A_n⟩$ 的每个分割点 $k$，递归计算 $m[i,k]+m[k+1,j]+p_{i-1}{p}_k{p}_j$，取最小值。

---

14.3 动态规划设计要素

小节	核心主题	关键结论
14.3 动态规划设计要素	DP四步法、最优子结构、重叠子问题	方法论

核心思路：DP的四个步骤——(1)刻画最优解结构、(2)递归定义最优解值、(3)自底向上计算、(4)构造最优解。两个关键性质：最优子结构（可用剪切-粘贴论证证明）和重叠子问题（可用子问题图分析）。

---

14.4 最长公共子序列

小节	核心主题	关键结论
14.4 最长公共子序列	序列DP、LCS-LENGTH、PRINT-LCS	$\Theta (mn)$

核心思路：定理14.1刻画LCS的最优子结构（三种情形），递归公式基于 $x_i$ 与 $y_j$ 是否相等分两种情况。LCS-LENGTH 填表 $\Theta (mn)$，PRINT-LCS 回溯 $O(m+n)$。

---

14.5 最优二叉搜索树

小节	核心主题	关键结论
14.5 最优二叉搜索树	区间DP、期望搜索代价	$\Theta (n^3)$，Knuth优化 $\Theta (n^2)$

核心思路：给定关键字搜索概率和哑关键字概率，构造使期望搜索代价最小的BST。递归公式 $e[i,j]={\min }_r\{e[i,r-1]+e[r+1,j]+w(i,j)\}$，与矩阵链乘法结构类似。

---

本章核心知识点

DP问题复杂度汇总

问题	子问题数	每个子问题选择数	时间复杂度	空间复杂度
钢条切割	$n$	$n$	$\Theta (n^2)$	$\Theta (n)$
矩阵链乘法	$O(n^2)$	$O(n)$	$\Theta (n^3)$	$\Theta (n^2)$
LCS	$O(mn)$	$O(1)$	$\Theta (mn)$	$\Theta (mn)$
最优BST	$O(n^2)$	$O(n)$	$\Theta (n^3)$	$\Theta (n^2)$

DP vs 其他算法范式

特性	动态规划	分治法	贪心法
子问题重叠	是	否	—
最优子结构	是	是	是
局部最优→全局最优	否	否	是
时间复杂度	多项式	多项式	多项式
典型问题	LCS、矩阵链乘法	归并排序、快速排序	活动选择、Huffman编码

DP问题分类

类型	特征	典型问题
线性DP	子问题为前缀/后缀	钢条切割、LIS
区间DP	子问题为连续区间	矩阵链乘法、最优BST
序列DP	子问题为两个序列的前缀	LCS、编辑距离
树形DP	子问题为子树	独立集、树的最优划分
状态压缩DP	用位掩码表示子集	旅行商问题(TSP)

---

与前序章节的知识关联

前序章节	关联方式
第12章 BST	14.5最优BST是BST的带权推广，考虑搜索频率
第13章 红黑树	红黑树保证最坏$O(\lg n)$但不考虑频率，最优BST考虑频率但不保证最坏情况
第11章 散列表	散列$O(1)$期望搜索 vs 最优BST的$O(\lg n)$期望搜索
第15章 贪心算法	DP与贪心法的对比是下一章的核心主题

---

学习路线

第14章学习路径：
  14.1 钢条切割（递归→备忘录法→自底向上→Θ(n²)分析）
    → 14.2 矩阵链乘法（区间DP→Θ(n³)→构造最优解）
      → 14.3 动态规划设计要素（四步法→最优子结构→重叠子问题→DP vs 分治/贪心）
        → 14.4 最长公共子序列（定理14.1→LCS-LENGTH→PRINT-LCS→Θ(mn)）
          → 14.5 最优二叉搜索树（期望代价→OPTIMAL-BST→Knuth优化→Θ(n²)）

学习建议

本章是算法设计部分的核心章节。14.1 是DP的入门（简单递归→备忘录→自底向上），重点理解”为什么备忘录法比朴素递归快”。14.2 是DP的第一个”真正”问题（区间DP），重点掌握填表顺序和构造最优解。14.3 是方法论总结，重点理解最优子结构的”剪切-粘贴”论证和重叠子问题的子问题图分析。14.4 LCS是考试高频题，重点掌握递归公式和回溯构造。14.5 最优BST与14.2结构类似，重点理解概率模型和Knuth优化。学完本章后，回顾第12-13章的BST和红黑树，理解”平衡BST保证最坏情况”与”最优BST优化期望情况”的设计取舍。

动态规划