AcWing 动态规划章节笔记

DP 这一章最重要的是定义状态，而不是先记答案。只要 f[i] 或 f[i][j] 的含义不清，后面的转移一定会乱。

本章核心模板

01 背包 / 完全背包

1
2
3
4
5
6
7
8
9
// 01 背包
for (int i = 1; i <= n; i++)
    for (int j = m; j >= v[i]; j--)
        f[j] = max(f[j], f[j - v[i]] + w[i]);

// 完全背包
for (int i = 1; i <= n; i++)
    for (int j = v[i]; j <= m; j++)
        f[j] = max(f[j], f[j - v[i]] + w[i]);

多重背包 / 分组背包

1
2
3
4
5
6
7
// 分组背包
for (int i = 1; i <= n; i++)
    for (int j = m; j >= 0; j--)
        for (int k = 0; k < (int)group[i].size(); k++) {
            int v = group[i][k].first, w = group[i][k].second;
            if (j >= v) f[j] = max(f[j], f[j - v] + w);
        }

LIS / LCS / 编辑距离

1
2
3
4
5
6
// O(n^2) LIS
for (int i = 1; i <= n; i++) {
    f[i] = 1;
    for (int j = 1; j < i; j++)
        if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
}

区间 DP

1
2
3
4
5
6
7
for (int len = 2; len <= n; len++)
    for (int l = 1; l + len - 1 <= n; l++) {
        int r = l + len - 1;
        f[l][r] = 1e9;
        for (int k = l; k < r; k++)
            f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
    }

状压 DP / 树形 DP / 记忆化搜索

1
2
3
4
5
6
7
8
9
10
// 树形 DP 例：没有上司的舞会
void dfs(int u) {
    f[u][1] = happy[u];
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        dfs(j);
        f[u][0] += max(f[j][0], f[j][1]);
        f[u][1] += f[j][0];
    }
}

本章题目与题解要点

背包问题

线性 DP

区间 DP

计数类 DP

数位统计 DP

状态压缩 DP

树形 DP

记忆化搜索

  • 901 滑雪：从每个点出发 DFS，结果记忆化。

这一章怎么复习

  1. 先牢固掌握 2、3、9 三个背包模板。
  2. 再做 895、897、902，把经典线性 DP 题打通。
  3. 最后用 282、291、285 三题补区间 DP、状压 DP 和树形 DP。

返回导航