第 3 章动态规划

本章定位：NOIP 几乎每年都有题目的正解或部分分是 DP。对你来说它有两层用处：一是背包、线性 DP 这种 T2 难度的题，要能直接写出正解；二是难题里“n ≤ 1000”“n ≤ 5000”那一档，往往就是留给不加任何优化的朴素 DP 的。背包的循环方向、区间 DP 的枚举顺序，都属于“学过但容易写反”的东西，和 Floyd 的 k 要放在最外层是同一类错误——本章每个模板里标了“倒序！”“正序！”“最外层”的地方，就是要背下来的地方。

3.1 DP 的四件事【必会】

一句话：把大问题拆成“规模小一点的同一类问题”，每个小问题只算一次，结果记在数组里。 识别信号：求最大、最小、方案数；一步一步做决定，而且“后面怎么选”只取决于当前的局面，不取决于是怎么走到这个局面的。

写任何 DP 之前，先在草稿纸上写清四件事：

	要回答的问题	以 01 背包为例
状态	数组的下标代表什么？存的值是什么？	f[i][j]：只考虑前 i 件物品、总重量不超过 j 时的最大价值
转移	最后一步有哪几种可能？各自从哪个更小的状态来？	第 i 件不选：f[i−1][j]；选：f[i−1][j−w] + v。取较大的
边界	最小的状态，值是多少？	f[0][j] = 0：一件都不考虑，价值是 0
顺序	算一个状态时，它要用的状态是不是都已经算好了？	i 从小到大

还有一件：答案在哪个状态里。背包是 f[n][W]；最长上升子序列是所有 f[i] 里最大的，不是 f[n]。

想不出状态时，从暴力搜索改过来：

先写暴力 DFS：dfs(i, rest) 表示“从第 i 件开始决定，背包还剩 rest 的容量，最多还能拿到多少价值”。
看 dfs 的参数：参数就是状态，参数的取值范围就是数组的大小。
加上记忆化（2.6 节），它已经是 DP 了。
想清楚计算顺序之后，把递归改成循环，就是常见的写法。

两条经验：

状态要记下“后面的决定需要知道的全部信息”，不多也不少。背包里后面只需要知道“还剩多少容量”，不需要知道“具体拿了哪几件”。
状态的个数 × 每个状态的转移数 = 复杂度。先算这个数，再动手。

3.2 线性 DP 【必会】

一句话：状态沿着序列从左往右推，f[i] 表示“以第 i 个元素结尾”或“只考虑前 i 个元素”时的答案。 识别信号：一个或两个序列，问最长、最大、方案数；n ≤ 5000 是在提示 O(n^2)。 复杂度：最长上升子序列 O(n^2)，可以优化到 O(n log n)；最长公共子序列 O(nm)。

最长上升子序列，状态是“以 a[i] 结尾”——转移时要知道最后一个数是谁，才能判断下一个数能不能接上：

// 最长上升子序列，O(n^2) 的 DP。洛谷 B3637 最长上升子序列（n ≤ 5000）。
#include <bits/stdc++.h>
using namespace std;

const int N = 5005;
int a[N], f[N];  // f[i]：以 a[i] 结尾的最长上升子序列有多长

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        f[i] = 1;                    // 边界：只有 a[i] 自己
        for (int j = 1; j < i; j++)  // 转移：接在前面某个比它小的 a[j] 后面
            if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
        ans = max(ans, f[i]);        // 答案不一定以最后一个数结尾，要在所有 f[i] 里取最大
    }
    cout << ans << '\n';
    return 0;
}

n 到 10^5 以上时用下面的写法【常考】。它换了一个角度：不记“以谁结尾”，而记“每种长度的子序列，结尾最小能是多少”。

// 最长上升子序列，O(n log n) 的写法。输入输出同洛谷 B3637，n 到 10^6 也能算。
// tail[k]：所有长度为 k + 1 的上升子序列里，结尾最小的那个结尾是多少。tail 一定是递增的，所以能二分。
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> tail;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        // 找第一个 >= x 的结尾，用 x 替换它：同样的长度，结尾更小，以后更容易接上别的数
        vector<int>::iterator it = lower_bound(tail.begin(), tail.end(), x);
        if (it == tail.end()) tail.push_back(x);  // x 比所有结尾都大：最长长度加 1
        else *it = x;
    }
    cout << (int)tail.size() << '\n';  // 求“最长不下降”时，把 lower_bound 换成 upper_bound
    return 0;
}

最长公共子序列，状态是“s 的前 i 个字符和 t 的前 j 个字符”：

// 最长公共子序列，O(nm) 的二维 DP。输入两行字符串（长度不超过 2000），输出它们的最长公共子序列的长度。
#include <bits/stdc++.h>
using namespace std;

const int N = 2005;
char s[N], t[N];
int f[N][N];  // f[i][j]：s 的前 i 个字符与 t 的前 j 个字符的最长公共子序列长度

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> (s + 1) >> (t + 1);  // 从下标 1 开始存，f 的第 0 行、第 0 列正好表示“空串”，值是 0
    int n = strlen(s + 1), m = strlen(t + 1);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (s[i] == t[j]) f[i][j] = f[i - 1][j - 1] + 1;  // 最后一个字符相同：配成一对
            else f[i][j] = max(f[i - 1][j], f[i][j - 1]);     // 不同：丢掉 s 的最后一个，或丢掉 t 的最后一个
        }
    cout << f[n][m] << '\n';
    return 0;
}

最大子段和（洛谷 P1115）：f[i] 是以 a[i] 结尾的最大连续和，f[i] = max(a[i], f[i−1] + a[i])。只用到前一个状态，一个变量就够：

long long cur = 0, best = LLONG_MIN;
for (int i = 1; i <= n; i++) {
    cur = max(cur, 0LL) + a[i];  // 前面的和是负的就丢掉，从 a[i] 重新开始
    best = max(best, cur);
}

易错点

最长上升子序列的答案是所有 f[i] 的最大值，不是 f[n]。
“上升”是严格的 <，“不下降”是 <=。O(n log n) 的写法里，分别对应 lower_bound 和 upper_bound。
O(n log n) 写法里的 tail 不是一个真实的子序列，只有它的长度有意义。
最长公共子序列里字符串要从下标 1 开始存：cin >> (s + 1)，长度是 strlen(s + 1)。从 0 开始存的话，f[i−1][j−1] 在 i = 0 时越界。
二维数组开多大。5000×5000 个 int 是 100 MB。开之前算一下：元素个数 × 4（int）或 × 8（long long），再除以 10^6，就是多少 MB，和题目的内存限制比一比。

练一练：洛谷 B3637 最长上升子序列、P1020 导弹拦截、P1115 最大子段和、P2758 编辑距离、P1439 【模板】最长公共子序列（O(n^2) 能拿一半分）。

3.3 背包【必会】

一句话：有若干物品和一个容量有限的背包，选一些装进去，让总价值最大。几种背包的区别只在“每种物品能拿几次”。 识别信号：“总时间 / 总重量 / 总花费不超过 W”，每样东西“选或不选”；物品数 × 容量不超过 10^8。 复杂度：O(物品数 × 容量)。

// 01 背包。洛谷 P1048 [NOIP2005 普及组] 采药：
// 总时间 T，m 株草药各有采摘时间和价值，每株最多采一次，求最大总价值。
#include <bits/stdc++.h>
using namespace std;

int f[1005];  // f[j]：总时间不超过 j 时能得到的最大价值

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T, m;
    cin >> T >> m;
    for (int i = 1; i <= m; i++) {  // 外层：一株一株地考虑
        int t, v;
        cin >> t >> v;
        for (int j = T; j >= t; j--)  // 内层倒序！此时 f[j - t] 还是“没考虑第 i 株”时的值，保证每株只用一次
            f[j] = max(f[j], f[j - t] + v);
    }
    cout << f[T] << '\n';
    return 0;
}

// 完全背包。洛谷 P1616 疯狂的采药：
// 总时间 t，m 种草药各有采摘时间和价值，每种可以采任意多次，求最大总价值。
#include <bits/stdc++.h>
using namespace std;

long long f[10000005];  // f[j]：总时间不超过 j 时的最大价值。答案能到 10^11，必须用 long long

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t, m;
    cin >> t >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        for (int j = a; j <= t; j++)  // 内层正序！此时 f[j - a] 可能已经采过第 i 种，正好表示“可以再采一次”
            f[j] = max(f[j], f[j - a] + b);
    }
    cout << f[t] << '\n';
    return 0;
}

// 分组背包。洛谷 P1757 通天之分组背包：
// 背包容量 m，n 件物品各有重量、价值和所属的组，同一组里最多选一件，求最大总价值。
#include <bits/stdc++.h>
using namespace std;

const int M = 1005;
int f[M];                           // f[j]：总重量不超过 j 时的最大价值
vector<pair<int, int> > group[M];   // group[g]：第 g 组里的物品（重量，价值）

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m, n;
    cin >> m >> n;
    int groups = 0;
    for (int i = 1; i <= n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        group[c].push_back(make_pair(a, b));
        groups = max(groups, c);
    }
    for (int g = 1; g <= groups; g++)                     // 第一层：组
        for (int j = m; j >= 0; j--)                      // 第二层：容量，倒序
            for (size_t k = 0; k < group[g].size(); k++)  // 第三层：这一组里挑哪一件
                if (j >= group[g][k].first)
                    f[j] = max(f[j], f[j - group[g][k].first] + group[g][k].second);
    cout << f[m] << '\n';
    return 0;
}

三种背包的循环方向：

	每种物品	容量 j 的方向	原因
01 背包	最多拿 1 次	从大到小	算 f[j] 时，f[j−w] 还是上一轮的旧值，这件物品还没被用过
完全背包	可以拿任意多次	从小到大	算 f[j] 时，f[j−w] 是这一轮已经更新过的新值，表示这种物品可以再拿一次
分组背包	每组最多拿 1 件	从大到小，并且“容量”的循环在“组内物品”的循环外面	对每个容量 j，在这一组里只挑最好的一件

为什么方向这么要紧：一维数组是把二维的 f[i][j] 去掉第一维、原地更新得到的。原地更新时，读到的是“旧值”还是“新值”完全取决于循环方向。拿不准的时候就写二维的 f[i][j]，不会错，只是多用些内存。

其他常见的变化，各记一句：

多重背包（第 i 种最多拿 c 次）：把 c 件拆成 1、2、4、……、剩下的这几捆，每一捆当成一件物品做 01 背包。比如 13 = 1 + 2 + 4 + 6，这四捆能凑出 0 到 13 的任何一个数量。
恰好装满：初值改成 f[0] = 0，其余都是负无穷（一个很小的负数）。最后 f[W] 还是负的，说明凑不出来。
求方案数：max 换成加法，f[0] = 1，转移是 f[j] = (f[j] + f[j - w]) % MOD。01 背包倒序、完全背包正序的规矩不变。NOIP 2018 货币系统的核心就是用完全背包判断“这个面额能不能被别的面额凑出来”。
两种限制（既限重量又限件数）：数组多开一维，两个容量都倒序。

易错点

01 背包的 j 写成了从小到大——它变成了完全背包，而且样例经常还能过。循环方向不是风格问题，写反了算法就是错的。
分组背包把“组内物品”的循环放到了“容量”的外面——同一组的物品会被各拿一件，变回了 01 背包。
j 的下界。01 背包写 j >= t；写成 j >= 0 又去访问 f[j - t] 就越界了（分组背包的模板里用 if 挡住了）。
f 数组的大小按容量开，不是按物品数开。
价值的总和超过 int。疯狂的采药的答案能到 10^11。
容量特别大（10^9）而总价值很小时【了解】：把状态反过来，f[v] 表示“凑出价值 v 最少要多少重量”。

练一练：洛谷 P1048 采药、P1616 疯狂的采药、P1757 通天之分组背包、P1049 装箱问题、P1776 宝物筛选（多重背包）、P5020 货币系统；本系统 E05。

3.4 区间 DP 【常考】

一句话：f[l][r] 表示把区间 [l, r] 处理完的最优结果，大区间的答案由它里面的两个小区间拼出来。 识别信号：每次操作的对象是“相邻的两个”或“连续的一段”（合并相邻的、消掉一段、切一刀）；n ≤ 300 ~ 500。 复杂度：O(n^3)。

// 区间 DP。洛谷 P1775 石子合并（弱化版）：
// n 堆石子排成一行，每次把相邻的两堆合成一堆，代价是这两堆的石子总数。求合并成一堆的最小总代价。
#include <bits/stdc++.h>
using namespace std;

const int N = 305;
int n, s[N];  // s[i]：前 i 堆的石子总数（前缀和）
int f[N][N];  // f[l][r]：把第 l 堆到第 r 堆合并成一堆的最小代价；f[i][i] = 0

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int m;
        cin >> m;
        s[i] = s[i - 1] + m;
    }
    for (int len = 2; len <= n; len++)            // 最外层枚举区间长度：短的先算好，长的才能用
        for (int l = 1; l + len - 1 <= n; l++) {  // 第二层枚举左端点
            int r = l + len - 1;
            f[l][r] = INT_MAX;                    // 求最小值之前先设成无穷大
            for (int k = l; k < r; k++)           // 第三层枚举最后一次合并的分界：[l, k] 和 [k + 1, r]
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
        }
    cout << f[1][n] << '\n';
    return 0;
}

三层循环的顺序是固定的：长度 → 左端点 → 分界点。先把所有长度为 2 的区间算完，再算长度为 3 的……因为 f[l][r] 用到的全是比它短的区间。

易错点

最外层枚举 l、第二层枚举 r：算 f[1][5] 的时候 f[3][5] 还没算。这又是“循环顺序”类的错误，最外层必须是长度。
初值。长度为 1 的区间 f[i][i] = 0（不用合并）；其余的在取 min 之前先设成无穷大。全局数组默认是 0，不设无穷大的话 min 出来永远是 0。
合并的代价是区间和，用前缀和一步算出。现场用循环去加，复杂度多一个 n。
石子围成一圈时：把数组复制一份接在后面，变成长度 2n 的一行，答案是所有长度为 n 的区间里最小的那个。
n = 5000 的题不可能是 O(n^3) 的区间 DP，别往这上面想。

练一练：洛谷 P1775 石子合并（弱化版）、P1880 石子合并（环形）、P1063 能量项链；本系统 E13。

3.5 状压 DP 【常考】

一句话：状态里要记“哪些元素已经用过”这样一个集合，而元素不超过 20 个时，用一个二进制整数表示这个集合，直接当数组下标。 识别信号：n ≤ 20，或者某个关键的量不超过 20（比如 E14 里要经过的检查点数 k ≤ 16）；全排列 n! 太慢，而 2^n·n^2 可以。NOIP 2016 愤怒的小鸟、2017 宝藏都是状压 DP，难题里“n ≤ 18”那一档也常常是它。 复杂度：旅行商 O(2^n·n^2)。n = 20 时实测 0.3 秒；数组有 2^20×20 个 int，约 80 MB。

// 状压 DP（旅行商）。洛谷 P1171 售货员的难题：
// n 个村庄（n ≤ 20），d[i][j] 是从 i 到 j 的路程。从 1 号出发，每个村庄恰好去一次，最后回到 1 号，求最短总路程。
// 用一个二进制数 S 记录“去过哪些村庄”：第 i 位是 1 表示去过 i 号（程序里村庄从 0 开始编号，起点是 0 号）。
#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
int n, d[20][20];
int f[1 << 20][20];  // f[S][i]：去过的集合是 S、现在停在 i 时，已经走过的最短路程

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) cin >> d[i][j];
    memset(f, 0x3f, sizeof(f));
    f[1][0] = 0;  // 边界：只去过起点，停在起点
    for (int S = 1; S < (1 << n); S++) {  // S 从小到大：转移只会往集合里加村庄，S 变大，用到的状态都已算好
        if (!(S & 1)) continue;           // 集合里必须有起点
        for (int i = 0; i < n; i++) {
            if (!(S >> i & 1) || f[S][i] == INF) continue;  // i 要在 S 里，而且这个状态走得到
            for (int j = 0; j < n; j++) {
                if (S >> j & 1) continue;  // j 已经去过
                int T = S | (1 << j);
                f[T][j] = min(f[T][j], f[S][i] + d[i][j]);
            }
        }
    }
    int ans = INF;
    for (int i = 0; i < n; i++)  // 所有村庄都去过之后，从 i 回到起点
        if (f[(1 << n) - 1][i] != INF) ans = min(ans, f[(1 << n) - 1][i] + d[i][0]);
    cout << ans << '\n';
    return 0;
}

和 2.3 节的全排列暴力比一比：全排列记住了完整的访问顺序，但后面的决定其实只需要知道“去过哪些、现在在哪”。顺序不同但这两样相同的走法，可以合并成一个状态。这就是 3.1 节说的“状态只留后面需要的信息”。

易错点

编号从 0 开始，第 i 位对应第 i 个元素。题目里的 1 号村庄，在程序里是 0 号。
边界写成 f[0][0] = 0。集合里必须已经有起点，是 f[1][0] = 0。
没判断 f[S][i] == INF 就往后转移，用一个走不到的状态更新了别人。
空间。n = 20 时 80 MB，先看内存限制；n ≤ 16 时只有 4 MB。
位运算的优先级（1.9 节）。if (S >> j & 1) 可以；if (S & 1 << j == 0) 是错的。

练一练：洛谷 P1171 售货员的难题、P1896 互不侵犯、P2831 愤怒的小鸟、P3959 宝藏；本系统 E14。

3.6 树形 DP 【常考】

状态定义在树的结点上：f[u] 表示以 u 为根的子树的答案，由各个儿子的答案合并而来。NOIP 2022、2024、2025 的 T3 都是树上的 DP 或计数，这一类是重点，内容放在第 6 章。

3.7 计数 DP 与取模【常考】

一句话：问“有多少种方案”时，转移从取最大值变成相加：f[i] 等于所有能一步走到 i 的状态的方案数之和。答案很大，题目会要求对一个数取模。 识别信号：“求方案数，对 10^9 + 7（或 998244353）取模”。NOIP 2021 数列、2024 遗失的赋值、2025 清仓甩卖都是计数题。 复杂度：和普通 DP 一样，状态数 × 转移数。

// 计数 DP + 取模 + 前缀和优化。
// n 级台阶，每一步可以上 1 到 k 级，问从地面走到第 n 级有多少种走法，答案对 10^9 + 7 取模。输入 n k。
// 朴素转移 f[i] = f[i-1] + f[i-2] + ... + f[i-k] 是 O(nk)；右边是连续一段的和，用前缀和就降到 O(n)。
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;
const int N = 1000005;
int f[N], s[N];  // f[i]：走到第 i 级的走法数；s[i] = f[0] + ... + f[i]。两者都已取模

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    f[0] = s[0] = 1;  // 边界：站在地面不动，算 1 种（不是 0 种）
    for (int i = 1; i <= n; i++) {
        int before = i - k - 1 >= 0 ? s[i - k - 1] : 0;  // f[i-k] 之前的那些不能要
        f[i] = (s[i - 1] - before + MOD) % MOD;          // 两个取过模的数相减可能是负数，要加 MOD 再取模
        s[i] = (s[i - 1] + f[i]) % MOD;
    }
    cout << f[n] << '\n';
    return 0;
}

取模的规矩（完整内容在第 7 章）：

运算	写法	不这样写会怎样
加	`(a + b) % MOD`
减	`(a - b + MOD) % MOD`	两个取过模的数相减可能是负数，C++ 里负数取模还是负数
乘	`1LL * a * b % MOD`	两个接近 10^9 的 `int` 相乘会溢出
除	不能直接除，要用逆元（第 7 章）

计数的两条原则：

不重不漏。每一种方案恰好被数到一次。设计转移时问自己“最后一步是什么”，按最后一步分类，各类之间不重叠。
边界通常是 f[0] = 1：“什么都不做”算一种方案。

易错点

f[0] 初始化成了 0，结果全是 0。
减法没加 MOD，输出了负数。小数据测不出来（数不够大，根本没取过模）。对策：把 MOD 临时改成 7 这样的小数，再跑小数据对拍。
写成 a + b % MOD，只给 b 取了模。
取最大值的 DP 不能一边取模一边比较，取模之后大小关系就乱了。
模数抄错。从题面复制，不要凭记忆敲。

练一练：洛谷 P1002 过河卒（计数 DP，不取模但要 long long）；本系统 E07（n, m ≤ 1000 的那一档就是网格上的计数 DP）。

3.8 期望 DP 【了解】

一句话：求“平均下来是多少”。状态和普通 DP 一样，转移时把各种可能的结果乘上各自的概率再相加。

NOIP 2016 换教室是代表：每节课可以申请换一间教室，申请以一定的概率通过，最多申请 m 次，求在教室之间走路的总路程的期望最小是多少。状态是 f[i][j][0/1]：前 i 节课、申请了 j 次、第 i 节有没有申请。转移时按“上一节通过或没通过 × 这一节通过或没通过”分情况，各乘上概率。教室之间的最短路要先用 Floyd 求出来——又是 Floyd。

现在只需要知道两点：期望可以拆开算（和的期望等于期望的和）；遇到期望题，小数据仍然可以用搜索把所有情况走一遍、按概率加权。

3.9 DP 优化入门【了解】

这一节是为了看懂部分分表。表里同时有“n ≤ 5000”和“n ≤ 10^5”两档时，前一档给朴素 DP，后一档才需要优化。先拿前一档。

滚动数组：f[i][…] 只用到 f[i−1][…] 时，只留两行，或者像背包那样压成一维。它只省内存，不省时间。
前缀和优化：转移是“一段连续状态的和”时（3.7 的走台阶），用前缀和把求和从 O(k) 变成 O(1)。
单调队列优化：转移是“一个滑动范围里的最大值或最小值”时，比如 f[i] = a[i] + max(f[i−k], …, f[i−1])，用单调队列每次 O(1) 取出最值（单调队列在第 5 章）。CSP-S 2019 划分用到了它。
数据结构优化：转移要在一个不规则的范围里取最值或求和时，用线段树或树状数组（第 5 章）。近年 NOIP 的 T4 里出现过这种做法，5.9 节有解释。

斜率优化、四边形不等式等不在目前的范围里，不用看。

3.10 DP 的部分分【必会】

朴素 DP 本身就是一档分。 数据范围表里“n ≤ 1000”“n ≤ 5000”这一档，多半就是给 O(n^2) 的 DP 的。状态设对了，转移慢一点没关系，先写出来交上去。
想不清计算顺序，就写记忆化搜索。 dfs 加一个数组，不用考虑循环怎么套。
DP 也要对拍。 用第 2 章的子集枚举或全排列当暴力。本章的背包模板就是和子集枚举对拍、旅行商就是和全排列对拍检查出来的。
调试的办法是把整张表打印出来。 对一个小样例，把 f 数组全部输出，和手算的表逐格对照，找第一个不一样的格子，错误就在那个格子的转移里。

看数据范围猜 DP 的类型：

数据范围	先想到
n ≤ 20	状压 DP
n ≤ 300 ~ 500	区间 DP，或三重循环的 DP
n ≤ 5000	O(n^2)：两维状态，或一维状态配 O(n) 的转移
物品数 × 容量 ≤ 10^8	背包
n ≤ 10^5 ~ 10^6	O(n) 或 O(n log n) 的线性 DP，多半要优化

本章必会清单

写 DP 之前，在纸上写出状态、转移、边界、顺序，以及答案在哪个状态里
最长上升子序列 O(n^2)，答案取所有 f[i] 的最大值
最长公共子序列，字符串从下标 1 开始存
01 背包（倒序）、完全背包（正序）、分组背包（组 → 容量倒序 → 组内物品），并说得出各自为什么是这个方向
区间 DP 的三层循环：长度 → 左端点 → 分界点，取 min 之前先设无穷大
旅行商的状压 DP：状态、边界 f[1][0] = 0、S 从小到大
取模四条：加、减（加 MOD）、乘（先 1LL *）、除（逆元）
把一个暴力 DFS 改写成记忆化搜索，再改成循环

第 3 章 动态规划

3.1 DP 的四件事 【必会】

3.2 线性 DP 【必会】

3.3 背包 【必会】

3.4 区间 DP 【常考】

3.5 状压 DP 【常考】

3.6 树形 DP 【常考】

3.7 计数 DP 与取模 【常考】

3.8 期望 DP 【了解】

3.9 DP 优化入门 【了解】

3.10 DP 的部分分 【必会】

本章必会清单

第 3 章动态规划

3.1 DP 的四件事【必会】

3.3 背包【必会】

3.7 计数 DP 与取模【常考】

3.9 DP 优化入门【了解】

3.10 DP 的部分分【必会】