动态规划（Dynamic Programming）
1. 核心思想
动态规划与分治法类似，都是把问题分解为规模更小的子问题。区别在于：分治法的子问题相互独立，而动态规划的子问题相互重叠——同一个子问题会在递归过程中被反复求解。动态规划把每个子问题的解记录在表中，需要时直接查表，从而把指数级的重复计算压缩为多项式级。
2. 两个基本要素
2.1 最优子结构（Optimal Substructure）
问题的最优解包含其子问题的最优解。这是能用动态规划求解的前提，也是写出递归关系式的依据。
证明思路：用「剪贴法（cut-and-paste）」反证——若子问题的解不是最优的，把它替换为最优子问题的解就能得到原问题更优的解，矛盾。
2.2 重叠子问题（Overlapping Subproblems）
递归求解过程中会反复遇到相同的子问题。若子问题互不重叠，则退化为分治法，用表反而浪费空间。
3. 两种实现方式
| 方式 | 方向 | 特点 |
|---|---|---|
| 备忘录法（自顶向下） | 从原问题递归，遇到未计算的子问题才求解并记录 | 代码贴近递归关系式，只计算真正用到的子问题 |
| 自底向上填表（迭代） | 从最小子问题出发，按规模递增填表 | 无递归栈开销，可做滚动数组等空间优化，便于分析复杂度 |
4. 解题四步法
- 刻画最优解的结构：明确「子问题是什么」，即状态的定义（例如
m[i][j]表示什么）。 - 建立递归关系：写出状态转移方程，并确定边界条件。
- 确定计算顺序：自底向上填表时，保证计算某个状态时它依赖的状态已经算出（通常是按区间长度、按物品数量递增）。
- 构造最优解（可选）：用额外的
s表或choice表记录决策，再回溯还原方案。
5. 典型问题
| 问题 | 状态定义 | 时间复杂度 |
|---|---|---|
| 矩阵连乘 | m[i][j]：计算 Ai..Aj 的最少乘法次数 | $O(n^3)$ |
| 最长公共子序列 | c[i][j]：X 前 i 个字符与 Y 前 j 个字符的 LCS 长度 | $O(mn)$ |
| 0-1 背包 | dp[i][j]：前 i 件物品、容量 j 的最大价值 | $O(nC)$ |
| 最大子段和 | dp[i]：以第 i 个元素结尾的最大子段和 | $O(n)$ |
| 最优二叉搜索树 | m[i][j]：由关键字 i..j 构成的最优 BST 平均查找代价 | $O(n^3)$ |
| 最长递增子序列 | dp[i]：以第 i 个元素结尾的 LIS 长度 | $O(n^2)$ / $O(n\log n)$ |
| 石子合并 | f[i][j]：合并区间 i..j 的最小/最大代价 | $O(n^3)$ |
| 编辑距离 | dp[i][j]：把前 i 个字符改成前 j 个字符的最少操作数 | $O(mn)$ |
评论