第 8 章动态规划#

本章目标：把动态规划拆成“状态、转移、边界、顺序、答案”五件事，避免只背模板。

8.1 学习目标#

理解重叠子问题和最优子结构。
能定义状态并写出转移方程。
掌握线性 DP、背包 DP、区间 DP、树形 DP、状态压缩 DP。
能判断遍历顺序和初始化。
能做基本空间优化和路径恢复。

8.2 DP 五步法#

状态： $dp[i]$ 表示什么？
转移：如何由旧状态推出新状态？
边界：最小问题答案是什么？
顺序：依赖的状态是否已经算出？
答案：最终取哪个状态？

如果状态定义含糊，后面都会乱。

8.3 线性 DP#

最长上升子序列 LIS：

状态： $dp[i]$ 表示以 $a_i$ 结尾的 LIS 长度。

转移：

dp[i]=1+\max_{j<i, a_j<a_i} dp[j]

答案：

\max_i dp[i]

复杂度 $O(n^2)$ 。可用二分优化到 $O(n\log n)$ ，但二分版本的数组含义不是最终答案本身，而是长度为 k 的上升子序列最小结尾。

8.4 背包 DP#

8.4.1 0/1 背包#

每件物品最多选一次。

状态： $dp[j]$ 表示容量 j 下最大价值。

转移：

dp[j]=\max(dp[j], dp[j-w_i]+v_i)

循环必须倒序：

1
for (int i = 0; i < n; i++) {
2
    for (int j = W; j >= w[i]; j--) {
3
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
4
    }
5
}

倒序保证每个物品只用一次。

8.4.2 完全背包#

每件物品可选无限次，容量循环正序：

1
for (int i = 0; i < n; i++) {
2
    for (int j = w[i]; j <= W; j++) {
3
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
4
    }
5
}

8.5 区间 DP#

区间 DP 常见状态：

dp[l][r] = \text{区间 } [l,r] \text{ 的最优值}

枚举长度：

1
for (int len = 2; len <= n; len++) {
2
    for (int l = 0; l + len - 1 < n; l++) {
3
        int r = l + len - 1;
4
        for (int k = l; k < r; k++) {
5
            dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r] + cost(l,r));
6
        }
7
    }
8
}

典型题：石子合并、矩阵链乘法、括号匹配。

8.6 树形 DP#

树形 DP 通常在 DFS 中完成。

例：树上最大独立集。

状态：

$dp[u][0]$ ：不选 u 的最大值。
$dp[u][1]$ ：选 u 的最大值。

转移：

dp[u][1] = weight[u] + \sum_{v \in child(u)} dp[v][0]

dp[u][0] = \sum_{v \in child(u)} \max(dp[v][0], dp[v][1])

8.7 状态压缩 DP#

当 n 小于 20 左右，可以用二进制表示集合。

TSP 状态：

dp[mask][i] = \text{已经访问集合 mask，当前在 i 的最小成本}

转移：

dp[mask \cup \{j\}][j] = \min(dp[mask \cup \{j\}][j], dp[mask][i] + w_{ij})

状态数： $2^n \cdot n$ 。

8.8 记忆化搜索#

当转移自然但顺序不好确定时，用记忆化搜索。

1
int dfs(state) {
2
    if (memo has state) return memo[state];
3
    ans = best over next states;
4
    memo[state] = ans;
5
    return ans;
6
}

它本质上也是 DP，只是计算顺序由递归决定。

8.9 易错点#

状态定义只写“表示答案”，不够具体。
初始化用 0，但实际应为无穷大或负无穷。
背包循环方向写反。
区间 DP 没按长度枚举。
树形 DP 没排除父节点。
状压 DP 位运算优先级写错。

8.10 练习#

写最长上升子序列 $O(n^2)$ 解法。
写 0/1 背包和完全背包。
写石子合并区间 DP。
写树上最大独立集。
写 TSP 状态压缩 DP。

ACM/OI 扩展：OI/ACM DP 优化与模型#

本节补充 OIer 和 ACMer 常用的算法套路、模板、复杂度分析和易错点。写模板时默认使用 C++17，变量名尽量短，但注释要说明不变量和适用条件。

1. DP 调试顺序#

DP 错误通常来自状态定义、初始化、顺序。

要点：

先用小数据手算表格。
把无穷大设为足够大但不会溢出。
确认答案是 dp[n]、max dp[i] 还是某个集合。
路径恢复需要保存 pre。

2. 多重背包二进制拆分#

数量为 c 的物品拆成 1,2,4,… 若干组。

1
for (auto [w, v, c] : items) {
2
    for (int k = 1; c > 0; k <<= 1) {
3
        int take = min(k, c);
4
        goods.push_back({w * take, v * take});
5
        c -= take;
6
    }
7
}
8
for (auto [w, v] : goods)
9
    for (int j = W; j >= w; --j)
10
        dp[j] = max(dp[j], dp[j - w] + v);

要点：

把多重背包转为 0/1 背包。
复杂度 $O(W\sum \log c_i)$ 。

3. DAG 上 DP#

拓扑序上转移，常用于最长路、方案数。

1
topo = topological_order();
2
dp[s] = 1;
3
for (int u : topo) {
4
    for (int v : g[u]) dp[v] += dp[u];
5
}

要点：

有环图不能直接做 DAG DP。
最长路在 DAG 上可做，在一般图上困难。

4. 斜率优化入门#

当转移形如直线取最值，可用凸包优化。

dp[i]=\min_{j<i}(dp[j]+a_j x_i+b_j)

要点：

每个 j 对应一条直线。
查询 x_i 上最小值。
若斜率和查询单调，可用单调队列维护凸壳。

常见坑：

推公式前不要套模板。
注意最小值/最大值和斜率单调方向。

5. 四边形不等式与 Knuth 优化#

区间 DP 的决策点若满足单调性，可减少枚举。

dp[l][r]=\min_{k\in[l,r)} dp[l][k]+dp[k+1][r]+w(l,r)

要点：

若最优决策 opt[l][r] 单调，可把 k 的范围缩小。
Knuth 优化可把部分区间 DP 从 $O(n^3)$ 降到 $O(n^2)$ 。

训练题型：

石子合并优化。
邮局选址类 DP 优化。

本章模板背诵清单#

能在 5 分钟内写出本章第一个核心模板。
能说出每个模板的时间复杂度和空间复杂度。
能说明模板不适用的反例。
能为模板构造 3 个边界样例。
能把模板改成 0-index 或 1-index 版本。

DP 模型扩展#

数位 DP#

统计 $[0,n]$ 中满足某种数字性质的数。

状态常含 position、tight、started、其他统计量。
tight 表示当前前缀是否贴着上界。
记忆化时 tight=true 通常不缓存。

概率 DP#

状态表示期望或概率。

E[x]=1+\sum_y P(x\to y)E[y]

期望从当前状态转移到后继。
若有自环，需要移项。
概率 DP 注意总概率为 1。

插头 DP#

网格连通性问题的高阶状态压缩。

按格子逐个扫描。
状态记录轮廓线连通性。
常用于铺砖、回路、连通块计数。

换根 DP#

先求以一个根为答案，再把根沿边移动。

第一次 DFS 求子树贡献。
第二次 DFS 把父侧贡献传给孩子。
常用于每个点到所有点距离和。

DP 优化判断清单#

先不要直接套高级优化。

转移是否可拆成只与 j 相关和只与 i 相关？
候选范围是否单调？
决策点是否单调？
代价函数是否满足凸性或四边形不等式？

高频模板训练卡#

这一组训练卡用于把“08_动态规划”转化为赛场识别能力。每张卡都包含题目信号、模板选择、复杂度、反例和实现检查。

卡 1：线性 DP#

题目信号：题目有阶段、选择、最优值或方案数，且符合线性 DP。
优先模板：先写线性 DP 的状态定义，再写转移。
核心不变量：状态含义明确，转移只依赖已经计算出的状态。
复杂度目标：复杂度 = 状态数 × 单状态转移数，优化后需重新计算。
不适用场景：后效性无法被状态覆盖、转移依赖未来时不适用。
实现检查：检查初始化、遍历顺序、无穷值、取模、滚动数组方向。
边界样例：空集、容量 0、单节点、无方案、最大状态。
训练题型：为线性 DP 写状态、转移、边界、顺序、答案五项。

卡 2：LIS#

题目信号：题目有阶段、选择、最优值或方案数，且符合 LIS。
优先模板：先写 LIS 的状态定义，再写转移。
核心不变量：状态含义明确，转移只依赖已经计算出的状态。
复杂度目标：复杂度 = 状态数 × 单状态转移数，优化后需重新计算。
不适用场景：后效性无法被状态覆盖、转移依赖未来时不适用。
实现检查：检查初始化、遍历顺序、无穷值、取模、滚动数组方向。
边界样例：空集、容量 0、单节点、无方案、最大状态。
训练题型：为 LIS 写状态、转移、边界、顺序、答案五项。

卡 3：LCS#

题目信号：题目有阶段、选择、最优值或方案数，且符合 LCS。
优先模板：先写 LCS 的状态定义，再写转移。
核心不变量：状态含义明确，转移只依赖已经计算出的状态。
复杂度目标：复杂度 = 状态数 × 单状态转移数，优化后需重新计算。
不适用场景：后效性无法被状态覆盖、转移依赖未来时不适用。
实现检查：检查初始化、遍历顺序、无穷值、取模、滚动数组方向。
边界样例：空集、容量 0、单节点、无方案、最大状态。
训练题型：为 LCS 写状态、转移、边界、顺序、答案五项。

卡 4：0/1 背包#

题目信号：题目有阶段、选择、最优值或方案数，且符合 0/1 背包。
优先模板：先写 0/1 背包的状态定义，再写转移。
核心不变量：状态含义明确，转移只依赖已经计算出的状态。
复杂度目标：复杂度 = 状态数 × 单状态转移数，优化后需重新计算。
不适用场景：后效性无法被状态覆盖、转移依赖未来时不适用。
实现检查：检查初始化、遍历顺序、无穷值、取模、滚动数组方向。
边界样例：空集、容量 0、单节点、无方案、最大状态。
训练题型：为 0/1 背包写状态、转移、边界、顺序、答案五项。

卡 5：完全背包#

题目信号：题目有阶段、选择、最优值或方案数，且符合完全背包。
优先模板：先写完全背包的状态定义，再写转移。
核心不变量：状态含义明确，转移只依赖已经计算出的状态。
复杂度目标：复杂度 = 状态数 × 单状态转移数，优化后需重新计算。
不适用场景：后效性无法被状态覆盖、转移依赖未来时不适用。
实现检查：检查初始化、遍历顺序、无穷值、取模、滚动数组方向。
边界样例：空集、容量 0、单节点、无方案、最大状态。
训练题型：为完全背包写状态、转移、边界、顺序、答案五项。

卡 6：多重背包#

题目信号：题目有阶段、选择、最优值或方案数，且符合多重背包。
优先模板：先写多重背包的状态定义，再写转移。
核心不变量：状态含义明确，转移只依赖已经计算出的状态。
复杂度目标：复杂度 = 状态数 × 单状态转移数，优化后需重新计算。
不适用场景：后效性无法被状态覆盖、转移依赖未来时不适用。
实现检查：检查初始化、遍历顺序、无穷值、取模、滚动数组方向。
边界样例：空集、容量 0、单节点、无方案、最大状态。
训练题型：为多重背包写状态、转移、边界、顺序、答案五项。

卡 7：分组背包#

题目信号：题目有阶段、选择、最优值或方案数，且符合分组背包。
优先模板：先写分组背包的状态定义，再写转移。
核心不变量：状态含义明确，转移只依赖已经计算出的状态。
复杂度目标：复杂度 = 状态数 × 单状态转移数，优化后需重新计算。
不适用场景：后效性无法被状态覆盖、转移依赖未来时不适用。
实现检查：检查初始化、遍历顺序、无穷值、取模、滚动数组方向。
边界样例：空集、容量 0、单节点、无方案、最大状态。
训练题型：为分组背包写状态、转移、边界、顺序、答案五项。

卡 8：区间 DP#

题目信号：题目有阶段、选择、最优值或方案数，且符合区间 DP。
优先模板：先写区间 DP 的状态定义，再写转移。
核心不变量：状态含义明确，转移只依赖已经计算出的状态。
复杂度目标：复杂度 = 状态数 × 单状态转移数，优化后需重新计算。
不适用场景：后效性无法被状态覆盖、转移依赖未来时不适用。
实现检查：检查初始化、遍历顺序、无穷值、取模、滚动数组方向。
边界样例：空集、容量 0、单节点、无方案、最大状态。
训练题型：为区间 DP 写状态、转移、边界、顺序、答案五项。

卡 9：树形 DP#

题目信号：题目有阶段、选择、最优值或方案数，且符合树形 DP。
优先模板：先写树形 DP 的状态定义，再写转移。
核心不变量：状态含义明确，转移只依赖已经计算出的状态。
复杂度目标：复杂度 = 状态数 × 单状态转移数，优化后需重新计算。
不适用场景：后效性无法被状态覆盖、转移依赖未来时不适用。
实现检查：检查初始化、遍历顺序、无穷值、取模、滚动数组方向。
边界样例：空集、容量 0、单节点、无方案、最大状态。
训练题型：为树形 DP 写状态、转移、边界、顺序、答案五项。

卡 10：换根 DP#

题目信号：题目有阶段、选择、最优值或方案数，且符合换根 DP。
优先模板：先写换根 DP 的状态定义，再写转移。
核心不变量：状态含义明确，转移只依赖已经计算出的状态。
复杂度目标：复杂度 = 状态数 × 单状态转移数，优化后需重新计算。
不适用场景：后效性无法被状态覆盖、转移依赖未来时不适用。
实现检查：检查初始化、遍历顺序、无穷值、取模、滚动数组方向。
边界样例：空集、容量 0、单节点、无方案、最大状态。
训练题型：为换根 DP 写状态、转移、边界、顺序、答案五项。

卡 11：DAG DP#

题目信号：题目有阶段、选择、最优值或方案数，且符合 DAG DP。
优先模板：先写 DAG DP 的状态定义，再写转移。
核心不变量：状态含义明确，转移只依赖已经计算出的状态。
复杂度目标：复杂度 = 状态数 × 单状态转移数，优化后需重新计算。
不适用场景：后效性无法被状态覆盖、转移依赖未来时不适用。
实现检查：检查初始化、遍历顺序、无穷值、取模、滚动数组方向。
边界样例：空集、容量 0、单节点、无方案、最大状态。
训练题型：为 DAG DP 写状态、转移、边界、顺序、答案五项。

卡 12：状态压缩 DP#

题目信号：题目有阶段、选择、最优值或方案数，且符合状态压缩 DP。
优先模板：先写状态压缩 DP 的状态定义，再写转移。
核心不变量：状态含义明确，转移只依赖已经计算出的状态。
复杂度目标：复杂度 = 状态数 × 单状态转移数，优化后需重新计算。
不适用场景：后效性无法被状态覆盖、转移依赖未来时不适用。
实现检查：检查初始化、遍历顺序、无穷值、取模、滚动数组方向。
边界样例：空集、容量 0、单节点、无方案、最大状态。
训练题型：为状态压缩 DP 写状态、转移、边界、顺序、答案五项。

卡 13：数位 DP#

题目信号：题目有阶段、选择、最优值或方案数，且符合数位 DP。
优先模板：先写数位 DP 的状态定义，再写转移。
核心不变量：状态含义明确，转移只依赖已经计算出的状态。
复杂度目标：复杂度 = 状态数 × 单状态转移数，优化后需重新计算。
不适用场景：后效性无法被状态覆盖、转移依赖未来时不适用。
实现检查：检查初始化、遍历顺序、无穷值、取模、滚动数组方向。
边界样例：空集、容量 0、单节点、无方案、最大状态。
训练题型：为数位 DP 写状态、转移、边界、顺序、答案五项。

卡 14：概率期望 DP#

题目信号：题目有阶段、选择、最优值或方案数，且符合概率期望 DP。
优先模板：先写概率期望 DP 的状态定义，再写转移。
核心不变量：状态含义明确，转移只依赖已经计算出的状态。
复杂度目标：复杂度 = 状态数 × 单状态转移数，优化后需重新计算。
不适用场景：后效性无法被状态覆盖、转移依赖未来时不适用。
实现检查：检查初始化、遍历顺序、无穷值、取模、滚动数组方向。
边界样例：空集、容量 0、单节点、无方案、最大状态。
训练题型：为概率期望 DP 写状态、转移、边界、顺序、答案五项。

卡 15：记忆化搜索#

题目信号：题目有阶段、选择、最优值或方案数，且符合记忆化搜索。
优先模板：先写记忆化搜索的状态定义，再写转移。
核心不变量：状态含义明确，转移只依赖已经计算出的状态。
复杂度目标：复杂度 = 状态数 × 单状态转移数，优化后需重新计算。
不适用场景：后效性无法被状态覆盖、转移依赖未来时不适用。
实现检查：检查初始化、遍历顺序、无穷值、取模、滚动数组方向。
边界样例：空集、容量 0、单节点、无方案、最大状态。
训练题型：为记忆化搜索写状态、转移、边界、顺序、答案五项。

卡 16：单调队列优化 DP#

题目信号：题目有阶段、选择、最优值或方案数，且符合单调队列优化 DP。
优先模板：先写单调队列优化 DP 的状态定义，再写转移。
核心不变量：状态含义明确，转移只依赖已经计算出的状态。
复杂度目标：复杂度 = 状态数 × 单状态转移数，优化后需重新计算。
不适用场景：后效性无法被状态覆盖、转移依赖未来时不适用。
实现检查：检查初始化、遍历顺序、无穷值、取模、滚动数组方向。
边界样例：空集、容量 0、单节点、无方案、最大状态。
训练题型：为单调队列优化 DP 写状态、转移、边界、顺序、答案五项。

卡 17：斜率优化 DP#

题目信号：题目有阶段、选择、最优值或方案数，且符合斜率优化 DP。
优先模板：先写斜率优化 DP 的状态定义，再写转移。
核心不变量：状态含义明确，转移只依赖已经计算出的状态。
复杂度目标：复杂度 = 状态数 × 单状态转移数，优化后需重新计算。
不适用场景：后效性无法被状态覆盖、转移依赖未来时不适用。
实现检查：检查初始化、遍历顺序、无穷值、取模、滚动数组方向。
边界样例：空集、容量 0、单节点、无方案、最大状态。
训练题型：为斜率优化 DP 写状态、转移、边界、顺序、答案五项。

卡 18：四边形不等式优化#

题目信号：题目有阶段、选择、最优值或方案数，且符合四边形不等式优化。
优先模板：先写四边形不等式优化的状态定义，再写转移。
核心不变量：状态含义明确，转移只依赖已经计算出的状态。
复杂度目标：复杂度 = 状态数 × 单状态转移数，优化后需重新计算。
不适用场景：后效性无法被状态覆盖、转移依赖未来时不适用。
实现检查：检查初始化、遍历顺序、无穷值、取模、滚动数组方向。
边界样例：空集、容量 0、单节点、无方案、最大状态。
训练题型：为四边形不等式优化写状态、转移、边界、顺序、答案五项。

卡 19：插头 DP#

题目信号：题目有阶段、选择、最优值或方案数，且符合插头 DP。
优先模板：先写插头 DP 的状态定义，再写转移。
核心不变量：状态含义明确，转移只依赖已经计算出的状态。
复杂度目标：复杂度 = 状态数 × 单状态转移数，优化后需重新计算。
不适用场景：后效性无法被状态覆盖、转移依赖未来时不适用。
实现检查：检查初始化、遍历顺序、无穷值、取模、滚动数组方向。
边界样例：空集、容量 0、单节点、无方案、最大状态。
训练题型：为插头 DP 写状态、转移、边界、顺序、答案五项。

卡 20：状压枚举子集#

题目信号：题目有阶段、选择、最优值或方案数，且符合状压枚举子集。
优先模板：先写状压枚举子集的状态定义，再写转移。
核心不变量：状态含义明确，转移只依赖已经计算出的状态。
复杂度目标：复杂度 = 状态数 × 单状态转移数，优化后需重新计算。
不适用场景：后效性无法被状态覆盖、转移依赖未来时不适用。
实现检查：检查初始化、遍历顺序、无穷值、取模、滚动数组方向。
边界样例：空集、容量 0、单节点、无方案、最大状态。
训练题型：为状压枚举子集写状态、转移、边界、顺序、答案五项。

卡 21：路径恢复#

题目信号：题目有阶段、选择、最优值或方案数，且符合路径恢复。
优先模板：先写路径恢复的状态定义，再写转移。
核心不变量：状态含义明确，转移只依赖已经计算出的状态。
复杂度目标：复杂度 = 状态数 × 单状态转移数，优化后需重新计算。
不适用场景：后效性无法被状态覆盖、转移依赖未来时不适用。
实现检查：检查初始化、遍历顺序、无穷值、取模、滚动数组方向。
边界样例：空集、容量 0、单节点、无方案、最大状态。
训练题型：为路径恢复写状态、转移、边界、顺序、答案五项。

卡 22：计数 DP#

题目信号：题目有阶段、选择、最优值或方案数，且符合计数 DP。
优先模板：先写计数 DP 的状态定义，再写转移。
核心不变量：状态含义明确，转移只依赖已经计算出的状态。
复杂度目标：复杂度 = 状态数 × 单状态转移数，优化后需重新计算。
不适用场景：后效性无法被状态覆盖、转移依赖未来时不适用。
实现检查：检查初始化、遍历顺序、无穷值、取模、滚动数组方向。
边界样例：空集、容量 0、单节点、无方案、最大状态。
训练题型：为计数 DP 写状态、转移、边界、顺序、答案五项。

本章赛前默写任务#

08_动态规划：详细训练清单#

本清单用于把章节知识拆成可执行的小任务，偏 OI/ACM 赛场使用。

训练点 1：线性 DP#

识别信号：题面出现与“线性 DP”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“线性 DP”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 2：LIS#

识别信号：题面出现与“LIS”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“LIS”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 3：LCS#

识别信号：题面出现与“LCS”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“LCS”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 4：0/1 背包#

识别信号：题面出现与“0/1 背包”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“0/1 背包”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 5：完全背包#

识别信号：题面出现与“完全背包”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“完全背包”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 6：多重背包#

识别信号：题面出现与“多重背包”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“多重背包”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 7：分组背包#

识别信号：题面出现与“分组背包”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“分组背包”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 8：区间 DP#

识别信号：题面出现与“区间 DP”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“区间 DP”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 9：树形 DP#

识别信号：题面出现与“树形 DP”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“树形 DP”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 10：换根 DP#

识别信号：题面出现与“换根 DP”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“换根 DP”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 11：DAG DP#

识别信号：题面出现与“DAG DP”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“DAG DP”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 12：状态压缩 DP#

识别信号：题面出现与“状态压缩 DP”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“状态压缩 DP”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 13：数位 DP#

识别信号：题面出现与“数位 DP”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“数位 DP”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 14：概率 DP#

识别信号：题面出现与“概率 DP”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“概率 DP”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 15：期望 DP#

识别信号：题面出现与“期望 DP”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“期望 DP”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 16：记忆化搜索#

识别信号：题面出现与“记忆化搜索”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“记忆化搜索”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 17：单调队列优化#

识别信号：题面出现与“单调队列优化”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“单调队列优化”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 18：斜率优化#

识别信号：题面出现与“斜率优化”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“斜率优化”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 19：线性 DP#

识别信号：题面出现与“线性 DP”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“线性 DP”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 20：LIS#

识别信号：题面出现与“LIS”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“LIS”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 21：LCS#

识别信号：题面出现与“LCS”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“LCS”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 22：0/1 背包#

识别信号：题面出现与“0/1 背包”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“0/1 背包”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 23：完全背包#

识别信号：题面出现与“完全背包”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“完全背包”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 24：多重背包#

识别信号：题面出现与“多重背包”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“多重背包”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 25：分组背包#

识别信号：题面出现与“分组背包”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“分组背包”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 26：区间 DP#

识别信号：题面出现与“区间 DP”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“区间 DP”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

ぬくぬくうちにゃ💤

第 8 章 动态规划#