返回：0400 算法设计与分析总目录 · 上一章：0405 Chap5 分治策略 · 下一章：0407 Chap7 网络流

1、学习目标

动态规划适合有重叠子问题和最优子结构的问题。它不是“背公式”，而是学会定义状态，把未来选择压缩成表格里的信息。

模块 要掌握的内容
DP 框架 状态、转移、初始化、顺序、答案
一维 DP 加权区间调度
二维 DP 背包、序列比对
区间 DP RNA 二级结构
图上 DP DAG 最短路、Bellman-Ford 思想

2、动态规划五步

  1. 定义状态：dp[i] 或 dp[i][j] 表示什么。
  2. 写转移：最后一步从哪里来。
  3. 初始化：空集、边界、不可达状态。
  4. 确定顺序：保证转移依赖已计算。
  5. 还原答案：只要值，还是要路径。

写 DP 最常见的错误是状态定义含糊。状态定义不清楚，转移式一定会乱。

3、加权区间调度

给定若干区间，每个区间有权重，选择互不重叠的区间使权重最大。

先按结束时间排序，令：

1
2
p(j) = 与区间 j 不冲突且结束最晚的区间编号
dp[j] = 前 j 个区间能取得的最大权重

转移：

1
dp[j] = max(dp[j-1], w_j + dp[p(j)])

含义：

  1. 不选第 j 个区间。
  2. 选第 j 个区间，则只能接 p(j) 之前的最优解。

p(j) 可用二分预处理，整体复杂度 O(n log n)。

4、分段最小二乘

给定一组点，用若干线段拟合，目标是误差和加上每条线段固定成本最小。

状态：

1
dp[j] = 拟合前 j 个点的最小代价

转移：

1
dp[j] = min_{1<=i<=j} { dp[i-1] + error(i, j) + C }

其中 error(i, j) 表示用一条直线拟合第 i 到第 j 个点的误差。

这个例子体现了 DP 的建模能力：最后一段从哪里开始，就是决策变量。

5、0/1 背包

每个物品只能选或不选，容量为 W。

状态：

1
dp[i][w] = 只考虑前 i 个物品，容量为 w 时的最大价值

转移：

1
2
dp[i][w] = dp[i-1][w]                                      不选 i
dp[i][w] = max(dp[i][w], dp[i-1][w-weight[i]] + value[i])   选 i

空间优化：

1
2
3
4
5
for (int i = 1; i <= n; ++i) {
    for (int w = W; w >= weight[i]; --w) {
        dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
    }
}

倒序遍历是为了保证每个物品只被选一次。

6、RNA 二级结构

RNA 二级结构可以抽象成区间 DP。令：

1
dp[i][j] = 区间 i..j 内最多能形成的合法配对数

转移思路：

  1. j 不参与配对：dp[i][j-1]。
  2. j 与某个 t 配对：dp[i][t-1] + 1 + dp[t+1][j-1]。

这种问题的特点是：一个选择会把区间切成左右两部分。

7、序列比对

两个字符串做全局比对，允许插入空位，目标是最小编辑或匹配代价。

状态：

1
dp[i][j] = A 的前 i 个字符和 B 的前 j 个字符的最小代价

转移：

1
2
3
4
5
dp[i][j] = min(
    dp[i-1][j-1] + match_or_mismatch,
    dp[i-1][j] + gap,
    dp[i][j-1] + gap
)

这是编辑距离、DNA 比对、文本 diff 的基础模型。

8、最短路中的 DP

DAG 最短路可以按拓扑序 DP：

1
dist[v] = min(dist[u] + w(u, v))

Bellman-Ford 也可以看作 DP：

1
dp[k][v] = 从源点到 v，最多使用 k 条边的最短距离

转移：

1
dp[k][v] = min(dp[k-1][v], dp[k-1][u] + w(u, v))

实际实现用松弛操作滚动优化。

9、DP 与贪心的区别

问题 贪心 DP
选择方式 每步做一个不可反悔选择 枚举所有可能选择
证明重点 贪心选择属于某个最优解 状态转移覆盖所有情况
常见复杂度 通常较低 可能更高
失败风险 局部最优不一定全局最优 状态设计错误会漏解

能贪心时优先考虑贪心；不能证明贪心时，尝试 DP。

10、易错点

易错点 修正
状态定义不完整 状态必须包含影响未来决策的信息
背包一维优化正序遍历 0/1 背包要倒序
忘记初始化不可达状态 不可达应设为正/负无穷
区间 DP 顺序错误 要按区间长度从小到大
只求值不记录路径 若要方案，需要额外记录选择

11、复盘清单

检查项 状态
能说出 DP 五步 待复盘
能写加权区间调度转移 待复盘
能解释 0/1 背包一维优化为什么倒序 待复盘
能写序列比对三种转移 待复盘
能识别区间 DP 的状态顺序 待复盘
能比较 DP 和贪心 待复盘