动态规划（Dynamic Programming）- 第4-5讲
北京大学软件研究所 屈婉玲 《算法设计与分析》课程 文字版PDF / PPT导出，69页 相关课程：算法分析与设计-第1讲-算法基础、算法分析与设计-第2讲-数学基础、算法分析与设计-第3讲-分治策略
一、动态规划基本思想
1.1 核心思想
动态规划的本质是多步判断求解最优化问题：
- 将问题分解为一系列子问题，每一步做出一个决策
- 每步决策对应一个子问题，子问题类型与原问题相同但规模更小
- 整个决策序列对应问题的最优解
1.2 优化原则（最优子结构性质）
一个最优决策序列的任何子序列本身，一定是相对于子序列初始和结束状态的最优决策序列。
满足优化原则 → 可以用动态规划 不满足优化原则 → 不能用动态规划
反例：总长模10的最小路径问题
- 目标：路径总长 mod 10 最小
- 全局最优解：下、下、下、下（模10结果）
- 动态规划给出的解：下、上、上、上
- 原因：子路径的最优并不构成全局最优，因为模运算破坏了最优子结构
1.3 动态规划 vs 分治
| 特性 | 分治 | 动态规划 |
|---|---|---|
| 子问题关系 | 独立不交叠 | 重叠（大量重复子问题） |
| 求解方式 | 递归分解，自顶向下 | 迭代填表，自底向上 |
| 子问题结果 | 合并即可 | 存储复用，避免重复计算 |
| 适用问题 | 子问题独立即可 | 需满足优化原则 + 子问题重叠 |
二、动态规划算法设计步骤
- 将问题表示成多步判断——分解为一系列子决策
- 确定优化函数和约束条件——以函数的极大/极小作为判断依据
- 列出递推方程和边界条件——核心数学模型
- 自底向上计算——从最小子问题开始填表
- 设立标记函数——记录最优决策路径，用于回溯构造解
- 时间/空间复杂度分析
三、经典应用实例
3.1 矩阵链乘法（Matrix Chain Multiplication）
问题：n个矩阵相乘 A₁A₂…Aₙ，Ai 为 Pᵢ₋₁×Pᵢ 阶矩阵，确定乘法顺序使元素相乘总次数最少。
输入：向量 P = <P₀, P₁, …, Pₙ>
实例：P = <10, 100, 5, 50>
- (A₁A₂)A₃：10×100×5 + 10×5×50 = 7,500 次
- A₁(A₂A₃)：10×100×50 + 100×5×50 = 75,000 次
- 相差10倍！
递推方程：
- m[i,j] = 计算 Aᵢ…Aⱼ 的最少相乘次数
- m[i,j] = min { m[i,k] + m[k+1,j] + Pᵢ₋₁ × Pₖ × Pⱼ } （i ≤ k < j）
- m[i,i] = 0 （边界条件）
Catalan数：n个矩阵的乘法次序数为第n个Catalan数
- C(n) = (1/(n+1)) × C(2n, n)
- 蛮力枚举复杂度 = Ω(4ⁿ / n
递归算法：直接递归，子问题大量重复计算，复杂度指数级
动态规划算法（非递归）：
- 按链长 r = 2 → n 逐步计算
- 时间复杂度：O(n³)
- 空间复杂度：O(n²)
- 标记函数 s[i,j] 记录最优划分位置 k
3.2 投资问题
问题：m元钱，n项投资，fᵢ(x) 表示将x元投入第i项的效益，求总效益最大的分配方案。
递推方程：
- Fₖ(x) = x元钱投给前k个项目的最大效益
- Fₖ(x) = max { fₖ(xₖ) + Fₖ₋₁(x - xₖ) } （0 ≤ xₖ ≤ x）
- F₁(x) = f₁(x) （边界）
复杂度：
- 时间：O(n × m²)（每项投资尝试0到x的所有分配）
- 空间：O(n × m)
3.3 背包问题（0-1背包）
问题：n种物品，第j种重量wⱼ、价值vⱼ，背包最大重量b，求最大价值。
递推方程：
- Fₖ(y) = 只装前k种物品、总重不超过y时的最大价值
- Fₖ(y) = max{ Fₖ₋₁(y), Fₖ₋₁(y - wₖ) + vₖ } （选或不选第k种）
- F₀(y) = 0，Fₖ(0) = 0 （边界）
标记函数：i(k,y) 记录 Fₖ(y) 对应的最后一件物品编号
- 若 Fₖ₋₁(y) ≥ Fₖ(y - wₖ) + vₖ，则 i(k,y) = i(k-1,y)
- 否则 i(k,y) = k
回溯构造解：从 i(n,b) 开始反向追踪每件物品是否被选。
复杂度：
- 时间：O(n × b)
- 空间：O(n × b)（可优化至 O(b)）
- 注：b是数值输入，若b很大则为伪多项式时间
3.4 最长公共子序列（LCS）
定义：X的子序列Z = 从X中删除若干元素（可不连续）后得到的序列
问题：给定 X = <x₁…xₘ>，Y = <y₁…yₙ>，求最长公共子序列。
关键定理：设Z是X和Y的LCS
- 若 xₘ = yₙ，则 zₖ = xₘ = yₙ，且 Zₖ₋₁ 是 Xₘ₋₁ 与 Yₙ₋₁ 的LCS
- 若 xₘ ≠ yₙ，则 Z 是 Xₘ₋₁ 与 Y 的LCS 或 X 与 Yₙ₋₁ 的LCS
递推方程：
- C[i,j] = Xᵢ 与 Yⱼ 的LCS长度
- C[i,j] = 0，若 i=0 或 j=0
- C[i,j] = C[i-1,j-1] + 1，若 xᵢ = yⱼ
- C[i,j] = max(C[i-1,j], C[i,j-1])，若 xᵢ ≠ yⱼ
算法：
- 填表：O(m × n) 时间，O(m × n) 空间
- 回溯：用 B[i,j] 标记箭头方向（↖ ↑ ←），从(m,n)回溯到(0,0)
3.5 图像压缩
问题：像素灰度序列 {p₁…pₙ}，灰度值 0~255（8位）。变位压缩：将序列分成m段，每段内用相同位数表示，段头附加11位（段长+位数），求总存储位数最小的分段方案。
递推方程：
- s[i] = 前i个像素的最优分段存储位数
- s[i] = min { s[i-k] + k × bmax(i-k+1, i) + 11 } （1 ≤ k ≤ min(i, 256)）
- s[0] = 0 （边界）
- 每段最多256个像素（因为段长用8位表示）
复杂度：时间 O(n)（每步最多256次比较，常数级），空间 O(n)
3.6 最大子段和
问题：n个整数（可负）的序列，求 Σa[k]（i≤k≤j）的最大值。
三种解法对比：
| 方法 | 时间复杂度 | 说明 |
|---|---|---|
| 蛮力枚举 | O(n³) | 枚举所有起点终点再求和 |
| 分治法 | O(n log n) | 左段/右段/跨中段，取最大值 |
| 动态规划 | O(n) | 在线算法，b[j]记录以j结尾的最大子段和 |
动态规划递推：
- b[j] = 以第j个元素结尾的最大子段和
- b[j] = max{ b[j-1] + a[j], a[j] }
- 最终答案 = max{ b[j] } （1 ≤ j ≤ n）
算法（Kadane算法）：
sum = 0; b = 0
for i = 1 to n:
if b > 0:
b = b + a[i]
else:
b = a[i]
if b > sum:
sum = b
return sum
时间 O(n)，空间 O(1)，动态规划中空间优化的极致。
3.7 凸多边形的三角划分
问题：凸n边形用n-3条内部不交对角线分成三角形，权函数W(三角形)，求总权最小的划分。
递推方程：
- t[i,j] = 顶点 vᵢ₋₁, vᵢ, …, vⱼ 构成的凸多边形的最优三角划分权值
- t[i,j] = min { t[i,k] + t[k+1,j] + W(vᵢ₋₁, vₖ, vⱼ) } （i ≤ k < j）
- t[i,i] = 0 （边界，退化为线段）
与矩阵链乘法同构：形式完全一致，都是区间DP，时间 O(n³)
3.8 电路布线
问题：n条导线，上端点1…n从左到右排列，下端点π(1)…π(n)是一个排列。导线(i, π(i))，求最大不相交导线子集。
相交条件：i < j 且 π(i) > π(j) → 两条导线相交
递推方程：
- Size(i,j) = 上端点≤i、下端点≤j 的最大不相交导线数
- 若 j < π(i)：Size(i,j) = Size(i-1, j) （第i条线不在集合中）
- 若 j ≥ π(i)：Size(i,j) = max{ Size(i-1,j), 1 + Size(i-1, π(i)-1) }
本质：等价于求排列 π 的最长递增子序列（LIS）——LIS 就是一组互不相交的导线。
复杂度：时间 O(n²)（可优化至 O(n log n)）
3.9 最优二叉搜索树
问题：n个排序元素 x₁<…<xₙ，存取概率 b₁…bₙ（命中）+ a₀…aₙ（未命中空隙），构造平均比较次数最小的二叉搜索树。
关键概念：
- 实结点：x₁…xₙ（存储数据，命中）
- 空隙结点：(-∞,x₁), (x₁,x₂), …, (xₙ,+∞)（未命中，叶结点）
- 平均比较次数 = Σbᵢ × depth(xᵢ) + Σaⱼ × depth(空隙j)
递推方程：
- m[i,j] = S[i,j] = {xᵢ…xⱼ} 对应的最优BST平均比较次数
- w[i,j] = aᵢ₋₁ + bᵢ + aᵢ + … + bⱼ + aⱼ （子树概率和）
- m[i,j] = min { m[i,k-1] + m[k+1,j] + w[i,j] } （i ≤ k ≤ j）
- m[i,i-1] = 0 （边界）
复杂度：时间 O(n³)，空间 O(n²)
- 利用Knuth优化可降至 O(n²)：根的选择范围随区间单调
3.10 RNA二级结构预测
问题：RNA序列 A,U,C,G 长度n，求最大碱基配对数的二级结构。
配对规则：
- A-U，C-G（Watson-Crick配对）
- 配对的碱基至少相隔4个位置：若(i,j)配对，则 i < j-4
- 每个碱基最多参与一对
- 无尖的转弯（没有伪结/pseudoknot）
递推方程：
- S[i,j] = 碱基序列 i…j 的最大配对数
- 若 j - i ≤ 4：S[i,j] = 0
- 否则两种情况：
- j不配对：S[i,j] = S[i, j-1]
- j与k配对（i ≤ k ≤ j-5）：S[i,j] = max { 1 + S[i, k-1] + S[k+1, j-1] }
复杂度：时间 O(n³)，空间 O(n²)
四、动态规划问题的共同特征
4.1 适用条件
- 优化原则（最优子结构）——必要条件，不满足则绝对不能用
- 子问题重叠——不是必要条件，但这是用DP比递归快的原因
- 无后效性——当前决策只依赖当前状态，不依赖未来决策
4.2 常见DP模型分类
| 模型 | 典型问题 | 状态维度 |
|---|---|---|
| 线性DP | 最大子段和、LIS | 1维 |
| 区间DP | 矩阵链乘法、凸多边形三角划分、最优BST | 2维（区间起止） |
| 背包DP | 0-1背包、投资问题 | 2维（物品数×容量） |
| 序列DP | LCS、编辑距离 | 2维（两序列下标） |
| 树形DP | 树的最大独立集 | 节点+选/不选 |
| 状态压缩DP | TSP、集合问题 | 位掩码集合 |
4.3 复杂度分析要点
- 时间复杂度 = 状态数 × 每个状态的决策数
- 空间复杂度 = 状态数（可滚动数组优化）
- 伪多项式时间：输入是数值（如背包容量b），实际随输入规模指数增长
五、设计要点总结
- 状态定义是关键——状态定义决定了递推方程是否简洁可解
- 从子问题到原问题——自底向上，从小规模逐步扩大
- 标记函数不要忘——求最优值容易，构造最优解需要回溯
- 空间优化常可能——很多问题只需保留前一行/前一列
- 验证优化原则——不满足优化原则的问题不能用DP
与其他知识的关联
- 算法分析与设计-第3讲-分治策略：分治与DP都分解子问题，但分治子问题独立，DP子问题重叠
- 算法分析与设计-第2讲-数学基础：递推方程求解、Master定理
- 《算法导论》-Introduction to Algorithms-第3版-CLRS：CLRS第15章动态规划、第16章贪心算法
- 贪心算法：贪心是DP的特例，每步局部最优即全局最优（需贪心选择性质+最优子结构）