Dynamic Programming

自动关联目录:Dynamic Programming

动态规划(DP)的本质:把穷举中的重复计算缓存下来。

穷举:  枚举所有方案,每个方案 O(n) 计算 → O(2^n · n)
DP:    发现不同方案共享"子方案" → 只算一次 → O(n · 状态数)

DP 的两个前提

  1. 最优子结构:问题的最优解包含子问题的最优解
  2. 子问题重叠:不同分支会重复计算同一个子问题

缺了最优子结构 → 不能用 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 背包

nn 个物品,重量wiw_i、价值viv_i,容量WW,每个最多选一次,求最大价值。

状态:dp[i][j] = 只考虑前ii 个物品、容量为jj 时的最大价值。

转移:

dp[i][j]=max⁡(dp[i−1][j], dp[i−1][j−wi]+vi)dp[i][j] = \max\big(dp[i-1][j],\ dp[i-1][j - w_i] + v_i\big)

(不选第ii 个 / 选第ii 个)

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]] 还是上一轮(i−1i-1)的值,没有被本轮更新过。如果正序,dp[j - w[i]] 可能已经包含了第ii 个物品 → 变成"完全背包"(每个物品可以选多次)。

完全背包就用正序(每个物品可无限选):

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]。

问题状态转移
最长上升子序列 LISdp[i] = 以 i 结尾的 LIS 长度dp[i]=max⁡j<i,aj<ai(dp[j])+1dp[i] = \max_{j<i, a_j<a_i}(dp[j]) + 1
最大子数组和dp[i] = 以 i 结尾的最大和dp[i]=max⁡(ai,dp[i−1]+ai)dp[i] = \max(a_i, dp[i-1] + a_i)
数字三角形dp[i][j]dp[i][j]=a[i][j]+max⁡(dp[i−1][j−1],dp[i−1][j])dp[i][j] = a[i][j] + \max(dp[i-1][j-1], dp[i-1][j])
股票买卖dp[i][0/1] = 第 i 天不持有/持有状态机转移

区间 DP

状态是区间 [i, j],转移通常枚举分割点。

dp[i][j]=min⁡i≤k<j(dp[i][k]+dp[k+1][j]+cost(i,j))dp[i][j] = \min_{i \le k < j}\big(dp[i][k] + dp[k+1][j] + \text{cost}(i,j)\big)

// 石子合并:合并相邻两堆的代价是它们的和,求最小总代价
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] 时,更小的区间都已算好。

复杂度O(n3)O(n^3),n≤500n \le 500 可接受。

树形 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];   // 访问过的集合 + 当前位置

复杂度O(2n⋅n2)O(2^n \cdot n^2),n≤20n \le 20。

数位 DP

统计区间[l,r][l, r] 中满足某种数字性质的数的个数。

// 状态:位置 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

E[u]=∑vP(u→v)⋅(E[v]+cost(u,v))E[u] = \sum_{v} P(u \to v) \cdot (E[v] + \text{cost}(u,v))

在图上通常需要解方程(高斯消元),因为有环。

背包变体

类型特点内层循环方向
0-1 背包每件最多一次倒序
完全背包每件无限次正序
多重背包每件cic_i 次二进制拆分 → 0-1;或单调队列优化
分组背包每组选一件组内倒序
二维费用背包两个约束维度dp[j][k],两个维度都倒序

DP 优化

优化适用效果
滚动数组只依赖上一层空间O(n)O(n) →O(1)O(1)
单调队列dp[i]=max⁡j∈[i−k,i−1]dp[j]+w(j)dp[i] = \max_{j \in [i-k, i-1]} dp[j] + w(j)O(nk)O(nk) →O(n)O(n)
斜率优化转移是一次的max⁡\max /min⁡\minO(n2)O(n^2) →O(n)O(n)
四边形不等式区间 DP 满足决策单调O(n3)O(n^3) →O(n2)O(n^2)
分治优化决策单调O(n2)O(n^2) →O(nlog⁡n)O(n \log n)
矩阵快速幂线性递推,n 很大O(n)O(n) →O(log⁡n)O(\log n)
前缀和优化转移是一个区间的和O(n2)O(n^2) →O(n)O(n)

先写出O(n2)O(n^2) 的朴素转移,再识别能否优化。绝大多数题目不需要高级优化。

判断"能不能用 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",初始化不同