动态规划（Dynamic Programming）

1. 核心思想

动态规划与分治法类似，都是把问题分解为规模更小的子问题。区别在于：分治法的子问题相互独立，而动态规划的子问题相互重叠——同一个子问题会在递归过程中被反复求解。动态规划把每个子问题的解记录在表中，需要时直接查表，从而把指数级的重复计算压缩为多项式级。

2. 两个基本要素

2.1 最优子结构（Optimal Substructure）

问题的最优解包含其子问题的最优解。这是能用动态规划求解的前提，也是写出递归关系式的依据。

证明思路：用「剪贴法（cut-and-paste）」反证——若子问题的解不是最优的，把它替换为最优子问题的解就能得到原问题更优的解，矛盾。

2.2 重叠子问题（Overlapping Subproblems）

递归求解过程中会反复遇到相同的子问题。若子问题互不重叠，则退化为分治法，用表反而浪费空间。

3. 两种实现方式

方式	方向	特点
备忘录法（自顶向下）	从原问题递归，遇到未计算的子问题才求解并记录	代码贴近递归关系式，只计算真正用到的子问题
自底向上填表（迭代）	从最小子问题出发，按规模递增填表	无递归栈开销，可做滚动数组等空间优化，便于分析复杂度

4. 解题四步法

1. 刻画最优解的结构：明确「子问题是什么」，即状态的定义（例如 m[i][j] 表示什么）。
2. 建立递归关系：写出状态转移方程，并确定边界条件。
3. 确定计算顺序：自底向上填表时，保证计算某个状态时它依赖的状态已经算出（通常是按区间长度、按物品数量递增）。
4. 构造最优解（可选）：用额外的 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)$

6. 学习目录

• 矩阵连乘问题