Dynamic Programming
自动关联目录:Dynamic Programming
动态规划(DP)的本质:把穷举中的重复计算缓存下来。
穷举: 枚举所有方案,每个方案 O(n) 计算 → O(2^n · n)
DP: 发现不同方案共享"子方案" → 只算一次 → O(n · 状态数)DP 的两个前提
- 最优子结构:问题的最优解包含子问题的最优解
- 子问题重叠:不同分支会重复计算同一个子问题
缺了最优子结构 → 不能用 DP(如最长路径问题在有正权环时没有最优子结构)。 缺了重叠 → 就是分治(如归并排序)。
三要素
| 要素 | 说明 | 类比 |
|---|---|---|
| 状态定义 | dp[i][j] 表示什么 | 函数签名 |
| 状态转移 | 从哪些状态推过来 | 递归关系 |
| 边界/初始化 | 最小规模的值 | base case |
状态定义是核心。定义错了,转移怎么写都别扭;定义对了,转移几乎是显然的。
解题流程
1. 先写暴力递归(自顶向下,明确"参数和返回值")
2. 发现重复计算 → 加记忆化(memo)
3. 把递归改写成递推(自底向上)—— 可选,但通常更快、更省空间
4. 空间优化(滚动数组)—— 可选强烈建议从递归 + 记忆化开始写。它逼你想清楚"状态是什么",而且不容易写错转移方向。
例:斐波那契
// 1. 暴力递归 O(2^n)
int fib(int n) {
if (n <= 1) return n;
return fib(n-1) + fib(n-2);
}
// 2. 记忆化 O(n)
int memo[100]; memset(memo, -1, sizeof memo);
int fib(int n) {
if (n <= 1) return n;
if (memo[n] != -1) return memo[n];
return memo[n] = fib(n-1) + fib(n-2);
}
// 3. 递推 + 滚动数组 O(n) 时间 O(1) 空间
int fib(int n) {
if (n <= 1) return n;
int a = 0, b = 1;
for (int i = 2; i <= n; i++) { int c = a + b; a = b; b = c; }
return b;
}递归树里 fib(3) 被算了几十次——这就是重叠子问题。
例:0-1 背包
个物品,重量、价值,容量,每个最多选一次,求最大价值。
状态:dp[i][j] = 只考虑前 个物品、容量为 时的最大价值。
转移:
(不选第 个 / 选第 个)
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= W; j++) {
dp[i][j] = dp[i-1][j]; // 不选
if (j >= w[i]) // 能选
dp[i][j] = max(dp[i][j], dp[i-1][j - w[i]] + v[i]);
}
}
cout << dp[n][W];空间优化:滚动数组
注意到 dp[i][*] 只依赖 dp[i-1][*],可以压成一维:
vector<int> dp(W + 1, 0);
for (int i = 1; i <= n; i++) {
for (int j = W; j >= w[i]; j--) // 关键:倒序!
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}为什么必须倒序:倒序保证 dp[j - w[i]] 还是上一轮()的值,没有被本轮更新过。如果正序,dp[j - w[i]] 可能已经包含了第 个物品 → 变成"完全背包"(每个物品可以选多次)。
完全背包就用正序(每个物品可无限选):
for (int i = 1; i <= n; i++)
for (int j = w[i]; j <= W; j++) // 正序
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);一个符号之差,语义完全不同。这是背包问题最经典的坑。
常见 DP 类型
线性 DP
状态沿一维序列推进:dp[i] 依赖 dp[i-1]、dp[i-2]… 或之前的某个 dp[j]。
| 问题 | 状态 | 转移 |
|---|---|---|
| 最长上升子序列 LIS | dp[i] = 以 i 结尾的 LIS 长度 | |
| 最大子数组和 | dp[i] = 以 i 结尾的最大和 | |
| 数字三角形 | dp[i][j] | |
| 股票买卖 | dp[i][0/1] = 第 i 天不持有/持有 | 状态机转移 |
区间 DP
状态是区间 [i, j],转移通常枚举分割点。
// 石子合并:合并相邻两堆的代价是它们的和,求最小总代价
for (int len = 2; len <= n; len++) // 枚举区间长度
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
dp[i][j] = INF;
for (int k = i; k < j; k++)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sum(i, j));
}循环顺序必须是"长度从小到大"——保证算 dp[i][j] 时,更小的区间都已算好。
复杂度, 可接受。
树形 DP
在树上做 DP,通常用 DFS 后序遍历。
// 没有上司的舞会:选一些节点,父子不能同时选,求最大权值和
void dfs(int u, int p) {
dp[u][1] = val[u]; // 选 u
dp[u][0] = 0; // 不选 u
for (int v : g[u]) {
if (v == p) continue;
dfs(v, u);
dp[u][1] += dp[v][0]; // 选 u → 子节点不能选
dp[u][0] += max(dp[v][0], dp[v][1]); // 不选 u → 子节点随便
}
}换根 DP:需要先算以某个根的答案,再做一次 DFS 把根"换"到子节点,用父的信息更新子。典型题:树上每个点到其他所有点的距离和。
状压 DP
状态里有集合,用 bitmask 表示。
// TSP
int dp[1 << N][N]; // 访问过的集合 + 当前位置复杂度,。
数位 DP
统计区间 中满足某种数字性质的数的个数。
// 状态:位置 pos、是否已贴上界 limit、前导零、已记录的信息
long long dfs(int pos, bool limit, ...) {
if (pos < 0) return /* 判定 */;
if (!limit && memo[pos][...] != -1) return memo[pos][...];
int up = limit ? digit[pos] : 9;
long long res = 0;
for (int d = 0; d <= up; d++)
res += dfs(pos - 1, limit && d == up, ...);
if (!limit) memo[pos][...] = res; // 只在 !limit 时记忆化
return res;
}关键:limit 状态不能记忆化(因为它是"贴着上界"的特殊路径,只出现一次)。
概率/期望 DP
在图上通常需要解方程(高斯消元),因为有环。
背包变体
| 类型 | 特点 | 内层循环方向 |
|---|---|---|
| 0-1 背包 | 每件最多一次 | 倒序 |
| 完全背包 | 每件无限次 | 正序 |
| 多重背包 | 每件 次 | 二进制拆分 → 0-1;或单调队列优化 |
| 分组背包 | 每组选一件 | 组内倒序 |
| 二维费用背包 | 两个约束维度 | dp[j][k],两个维度都倒序 |
DP 优化
| 优化 | 适用 | 效果 |
|---|---|---|
| 滚动数组 | 只依赖上一层 | 空间 → |
| 单调队列 | → | |
| 斜率优化 | 转移是一次的 / | → |
| 四边形不等式 | 区间 DP 满足决策单调 | → |
| 分治优化 | 决策单调 | → |
| 矩阵快速幂 | 线性递推,n 很大 | → |
| 前缀和优化 | 转移是一个区间的和 | → |
先写出 的朴素转移,再识别能否优化。绝大多数题目不需要高级优化。
判断"能不能用 DP"
能否定义出一个"规模更小"的子问题,且原问题的最优解由子问题的最优解拼成?
✓ → DP
✗ → 可能要贪心、搜索、网络流、或其他模型反例:最长简单路径(有正环时)——子问题"从 A 到 B 的最长路径"和"从 B 到 C 的最长路径"拼起来可能有重复节点,不是合法解 → 没有最优子结构 → NP-hard。
常见坑
- 状态定义不清就写转移:先写清楚
dp[...]的中文含义 - 初始化错误:求 max 初始化为
-INF,求 min 初始化为INF,求方案数时dp[0] = 1。还要注意"不可达"和"值为 0"的区别 - 转移顺序错:滚动数组的正序/倒序;区间 DP 的长度从小到大的顺序
- 边界没处理:
i=0、j=0往往要特殊判断 - 记忆化的
-1判断:如果答案本身可能是-1,要用单独的vis[]数组 - 整数溢出:方案数类 DP 极易爆
int,用long long - 树形 DP 忘了跳过父节点:会无限递归
- 状压 DP 的空间:
dp[1<<20][20]是 80 MB,注意内存限制 - 滚动数组时忘了清零:复用数组时上一轮的残留值会污染结果
- 把"恰好"和"不超过"搞混:
dp[j]表示"容量恰好 j"还是"容量不超过 j",初始化不同