动态规划
动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
能用动态规划解决的问题,需要满足三个条件:最优子结构,无后效性和子问题重叠。
原理
最优子结构
具有最优子结构也可能是适合用贪心的方法求解。
注意要确保我们考察了最优解中用到的所有子问题。
- 证明问题最优解的第一个组成部分是做出一个选择;
- 对于一个给定问题,在其可能的第一步选择中,假定你已经知道哪种选择才会得到最优解。你现在并不关心这种选择具体是如何得到的,只是假定已经知道了这种选择;
- 给定可获得的最优解的选择后,确定这次选择会产生哪些子问题,以及如何最好地刻画子问题空间;
- 证明作为构成原问题最优解的组成部分,每个子问题的解就是它本身的最优解。方法是反证法,考虑加入某个子问题的解不是其自身的最优解,那么就可以从原问题的解中用该子问题的最优解替换掉当前的非最优解,从而得到原问题的一个更优的解,从而与原问题最优解的假设矛盾。
要保持子问题空间尽量简单,只在必要时扩展。
最优子结构的不同体现在两个方面:
- 原问题的最优解中涉及多少个子问题;
- 确定最优解使用哪些子问题时,需要考察多少种选择。
子问题图中每个定点对应一个子问题,而需要考察的选择对应关联至子问题顶点的边。
无后效性
已经求解的子问题,不会再受到后续决策的影响。
子问题重叠
如果有大量的重叠子问题,我们可以用空间将这些子问题的解存储下来,避免重复求解相同的子问题,从而提升效率。
基本思路
对于一个能用动态规划解决的问题,一般采用如下思路解决:
- 将原问题划分为若干 阶段,每个阶段对应若干个子问题,提取这些子问题的特征(称之为 状态);
- 寻找每一个状态的可能 决策,或者说是各状态间的相互转移方式(用数学的语言描述就是 状态转移方程)。
- 按顺序求解每一个阶段的问题。
记忆化搜索
记忆化搜索是一种通过记录已经遍历过的状态的信息,从而避免对同一状态重复遍历的搜索实现方式。
因为记忆化搜索确保了每个状态只访问一次,它也是一种常见的动态规划实现方式。
背包 DP
0-1 背包问题
只有两种可能的状态(取与不取)
状态转移方程:
for (int i = 1; i <= n; i++)
for (int l = W; l >= w[i]; l--)
f[l] = max(f[l], f[l - w[i]] + v[i]); // 状态方程完全背包
完全背包模型与 0-1 背包类似,与 0-1 背包的区别仅在于一个物品可以选取无限次,而非仅能选取一次。
差别只体现在容量的遍历方向:
for (int i = 1; i <= n; i++)
for (int l = w[i]; l <= W; l++) // 注意:正序
f[l] = max(f[l], f[l - w[i]] + v[i]);| 遍历方向 | 原因 | |
|---|---|---|
| 0-1 背包 | 容量逆序 | 保证 f[l - w[i]] 还是"上一轮(未选过 i)"的状态 |
| 完全背包 | 容量正序 | 让 f[l - w[i]] 已经包含了选过 i 的状态,从而可以重复选 |
这一行方向写反,是背包题最常见的错误,而且样例经常还能过。
多重背包
每件物品最多取 c[i] 次。最直接的写法多一维枚举次数,复杂度 O(n·W·c);标准优化是二进制拆分:
把 13 件拆成 1 + 2 + 4 + 6 四组
每组视作一个独立的 0-1 物品 → 转化回 0-1 背包
复杂度降到 O(n·W·log c)数据量再大时用单调队列优化降到 O(n·W)。
分组背包
物品分成若干组,每组最多选一个。循环顺序是:组 → 容量 → 组内物品。
for (int g = 1; g <= G; g++) // 组
for (int l = W; l >= 0; l--) // 容量(逆序)
for (auto& item : group[g]) // 组内物品
if (l >= item.w)
f[l] = max(f[l], f[l - item.w] + item.v);容量循环必须在物品循环之外,否则同一组会被选多个。
其它常见模型
| 模型 | 状态设计 | 典型题 |
|---|---|---|
| 线性 DP | f[i] 前缀/位置 | LIS、最大子段和、数字三角形 |
| 区间 DP | f[l][r] 区间 | 石子合并、括号匹配、戳气球 |
| 树形 DP | f[u][s] 子树状态 | 树的最大独立集、树形背包 |
| 状压 DP | f[S] 集合位掩码 | TSP、集合覆盖 |
| 数位 DP | f[pos][tight][...] | 区间内满足某性质的数的个数 |
| 概率/期望 DP | 期望值作状态 | 随机游走、博弈期望 |
区间 DP
特征:合并/分割一段区间,大区间由小区间拼出来
状态:f[l][r] = 区间 [l, r] 的最优值
转移:枚举分割点 k,f[l][r] = opt(f[l][k] + f[k+1][r] + cost(l,r))
顺序:按区间长度从小到大树形 DP
特征:答案依赖子树,且子树之间互不干扰
状态:f[u][0/1] 之类,"u 选/不选" 或 "u 子树内选了几个"
实现:一次 DFS,后序合并子树结果
注意:树上背包要把"子树大小"作为容量上界,否则复杂度退化到 O(n³)状压 DP
特征:n ≤ 20 左右,状态是一个集合
编码:一个 int 的二进制位表示"哪些元素已被选"
转移:枚举子集,或按位逐个加入
优化:子集枚举 for (S = T; S; S = (S-1) & T) 是 O(3^n) 而不是 O(4^n)常见优化
| 优化 | 适用 |
|---|---|
| 滚动数组 | 状态只依赖上一层,把第一维压掉(背包就是典型) |
| 前缀和/差分优化 | 转移是一个区间的和 |
| 单调队列优化 | 转移形如 max(f[j]),j 在滑动窗口内 |
| 斜率优化 / 凸包 | 转移可化为一次函数取最值 |
| 决策单调性 / 分治优化 | 最优决策点单调 |
| 矩阵快速幂 | 线性递推且 n 极大 |
| 剪枝 + 记忆化 | 状态空间大但可达状态少,见上文记忆化搜索 |
优先写对再优化:先写出 O(n·W) 的朴素版本,确认状态定义与转移无误,再考虑优化。多数题目朴素版已经够用。
解题套路
1. 判断:有没有最优子结构 + 无后效性 + 子问题重叠
2. 定义状态:问自己"还差什么信息就能唯一确定这个子问题"
3. 写转移:枚举最后一步/分割点/选择
4. 定顺序:保证计算 f[i] 时它依赖的状态已算出
5. 初始化:合法起点赋值,其余设 ±∞
6. 优化:空间压缩、转移优化核心在第 2 步——状态定义错了,后面全白做。检验方法:这个状态能不能唯一确定子问题,且转移能不能覆盖所有可能。
与其它方法的关系
| 动态规划 | 贪心 | 分治 | 记忆化搜索 | |
|---|---|---|---|---|
| 子问题 | 重叠 | 无重叠(每步只留一个) | 无重叠 | 重叠 |
| 决策 | 枚举所有转移取最优 | 直接选局部最优 | 按结构递归 | 枚举 |
| 正确性 | 状态转移方程 | 需要贪心选择性质证明 | 结构归纳 | 同 DP |
分治与 DP 的分界是子问题是否重叠:不重叠用分治(归并排序),重叠用 DP(斐波那契)。记忆化搜索与递推是同一个 DP 的两种实现,前者按"需要"算、后者按"顺序"算。
常见坑
| 坑 | 说明 |
|---|---|
| 背包容量遍历方向写反 | 0-1 与完全背包混淆 |
| 状态定义遗漏维度 | 无法覆盖全部情况,答案偏小/偏大 |
| 初始化不对 | 求 max 却初始化成 0,导致非法状态参与转移 |
| 转移顺序错误 | 依赖的状态还没算出来 |
| 边界没处理 | f[0]、空区间、单元素区间 |
| 数组开小 / 越界 | l - w[i] 为负时没有判断 |
| 空间不压缩导致 MLE | 二维可以压一维时务必压 |