动态规划 知识点讲解

🎯 先搞清楚它是什么

📌 考纲要求（NOI 大纲 · 动态规划 / 参考《cspNOI级大纲解读》）：考纲在“动态规划”部分列出“基于连通性状态压缩的动态规划模型”“双重动态规划”等进阶内容，并指出在虚树等结构上“做动态规划求得本次询问的结果”。本讲对齐“动态规划”这一基础考点：用“状态 + 转移 + 边界”解决具有最优子结构、无后效性的计数与最值问题。

动态规划（Dynamic Programming, DP） 是把一个复杂问题拆成若干阶段，每个阶段做一个决策，并用“之前阶段算出的结果”推导出“当前结果”的方法。

它成立依赖两个性质：

• 最优子结构：全局最优解包含局部最优解；
• 无后效性：一旦某个阶段的状态确定，它之后怎么发展只和这个状态有关，和“怎么走到这个状态”无关。

⚠️ 一句话：DP 就是“把暴力搜索里重复算的子问题存起来（记忆化），或者自底向上一步步推”。看到“求最值 / 方案数 / 计数 + 有明显阶段”先想 DP。

🧩 关键规则与结论

DP 三要素（写题必想）：

1. 状态定义：dp[i] / dp[i][j] 表示“什么条件下的最优值/方案数”；

2. 状态转移方程：dp[i] = f(dp[之前的若干状态])；

3. 边界 / 初始化：最小子问题的答案（如 dp[0]=0）。

三种常见形态：

🗺️ 知识用法地图

🔬 推演：为什么这些写法是对的（以及它们能用来干什么）

推演 1 · 为什么“存子问题结果”能指数级加速

以斐波那契式递归 f(n)=f(n-1)+f(n-2) 为例：朴素递归会重复算 f(n-2) 无数次，复杂度指数级。DP 的核心就是每个子问题只算一次：自顶向下用 memo[] 记忆化，或自底向上用数组 dp[] 顺序推。状态数从指数降到 O(n)。这就是 DP 省时间的本质——消除重复计算。

📌 用法：先写出“暴力递推式”，再加记忆化（或改循环）就是 DP；这是设计 DP 的通用起点。

推演 2 · 为什么 01 背包要“容量倒序”更新

dp[j] = max(dp[j], dp[j-w]+v) 表示“用第 i 个物品，容量 j 时的最优”。若正序遍历 j，那么 dp[j-w] 可能已经被同一个物品 i 更新过（前面刚算的），相当于一件物品用了多次 → 变成完全背包。只有倒序（从大到小）遍历 j，dp[j-w] 用的才是“没放第 i 件”的旧值，保证每件最多用一次 → 01 背包。

📌 用法：01 背包容量倒序，完全背包容量正序。这一行顺序错了，题型就变了。

推演 3 · 为什么树形 DP 要“后序（先儿子后父亲）”

树形 DP 的状态通常在“以 u 为根的子树”上。要算 u，必须先算好它所有儿子 v 的子树答案（儿子不依赖父亲），所以遍历顺序是后序：先递归处理孩子，回到 u 时再把孩子们的结果合并。这正好满足“无后效性”——u 的状态只由已算好的孩子决定。

📌 用法：树形 DP 几乎都是 dfs(u) 里先 for v in children: dfs(v)，再在 u 处用 dp[v] 合并出 dp[u]。

🔧 编程题里怎么考、怎么用？

① 它在编程题里长什么样（考法总览）

② 识别信号清单：看到什么该想到 DP

• “最优 / 最大 / 最小 / 最长 / 最多方案” → DP 候选；
• “有阶段、有决策、前面决定后面” → 线性/背包 DP；
• “选若干物品受总量限制” → 背包；
• “合并相邻 / 区间最优” → 区间 DP；
• “树上的点，选或不选、父子约束” → 树形 DP；
• 若“当前决策依赖未来”或“状态会无限细分”则 DP 难做，可能要贪心/搜索。

判断步骤：

① 问题能拆成阶段、有重复子问题吗？→ DP
② 状态怎么定义（一维/二维）？→ 写 dp[i] / dp[i][j]
③ 转移方程 + 边界？→ 先暴力记忆化再优化

③ 必背模板：01 背包（一维优化）

int dp[V + 1] = {0};                       // dp[j] = 容量 j 下的最大价值
for (int i = 1; i <= n; i++) {             // 枚举每个物品
    for (int j = V; j >= w[i]; j--)        // ⭐ 容量倒序（保证每件最多用一次）
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
cout << dp[V];

④ 必背模板：数字三角形（线性 DP）

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i; j++)
        dp[i][j] += max(dp[i-1][j-1], dp[i-1][j]);   // 从正上 / 左上 转移
cout << max(dp[n][1..n]);

⑤ 思路点拨：拿到题第一步想什么

1. 先定义状态：dp[...] 到底表示“到哪、满足什么条件下”的什么值；

2. 找最后一步决策：当前状态由哪几个“更早状态”推来，写出转移；

3. 定边界：最小子问题（0 个物品 / 起点）的值；

4. 选遍历顺序：背包倒序、区间先枚举长度、树形后序；

5. 先写记忆化搜索再转循环，往往比直接推循环更不容易错。

📚 更多同类真题（来自真题库，点击展开）

🔍 看一个例子

例：01 背包（P1048 采药思路）—— n 株草药，每株耗时 w、价值 v，总时间 m，求最大价值。

#include <iostream>
#include <algorithm>
using namespace std;
int dp[1005];                       // dp[j]：用了 j 时间的最大价值
int main() {
    int m, n; cin >> m >> n;       // m 总时间，n 株草药
    for (int i = 1; i <= n; i++) {
        int w, v; cin >> w >> v;
        for (int j = m; j >= w; j--)            // ⭐ 容量倒序
            dp[j] = max(dp[j], dp[j - w] + v);   // 选这株 vs 不选
    }
    cout << dp[m] << '\n';
    return 0;
}

为什么倒序？见推演 2：倒序保证 dp[j-w] 还没被“当前这株”更新过，于是每株最多采一次。把 j >= w 改成 j >= 0 正序遍历，就成了“每株可无限采”的完全背包（P1616 疯狂的采药）。

下面对照一张图理解“状态转移表”：

🪤 常见错误

1. 状态定义不清：dp 到底表示什么没想明白就写，转移必然错；先口头说清再写。

2. 01 背包容量正序遍历：写成 for j=w..V 会变成完全背包（同物多用），要 for j=V..w 倒序。

3. 忘记初始化边界：dp 数组默认全 0，但求“最长”类有时要 dp[i]=1 起步，漏了答案偏小。

4. 转移顺序错：区间 DP 必须先枚举区间长度再枚举左端点，否则用到的子区间还没算。

5. 树形 DP 用儿子前没先递归：必须在 dfs(v) 返回后再合并，否则儿子状态是空的。

6. 数组开小 / 下标越界：容量维度要开到 V+1，状态维数算错会 RE 或 WA。

7. 混淆 DP 与贪心：能贪心的前提更强（局部最优→全局最优），很多题贪心是错的，老老实实 DP。

✅ 自测

1. 动态规划成立依赖哪两个性质？各用一句话解释。

2. DP 三要素是什么？写题时按什么顺序想？

3. 01 背包为什么容量要“倒序”遍历？改成“正序”会变成什么背包？

4. 数字三角形 dp[i][j] 的转移来自哪两个位置？为什么？

5. 区间 DP 为什么必须先枚举“区间长度”？

6. 树形 DP 为什么用“后序（先儿子后父亲）”的 DFS 顺序？

7. 看到“求最值 + 有阶段有决策”的题，你的第一步设计动作是什么？

这个模型讲什么

线性 DP 是 DP 的入门形态：状态沿一条序列（或一条路径）递推，每一步由“前面若干状态”转移来。

数字三角形（P1216）：dp[i][j] 表示从顶走到第 i 行第 j 列的最大和。

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i; j++)
        dp[i][j] += max(dp[i-1][j-1], dp[i-1][j]);   // 来自正上 / 左上

最大子段和（P1115）：dp[i] = 以第 i 个数结尾的最大子段和。

dp[i] = max(a[i], dp[i-1] + a[i]);     // 要么自己开头，要么接上前面
ans = max(ans, dp[i]);

过河卒（P1002）：dp[i][j] = dp[i-1][j] + dp[i][j-1]（从左边/上边来），注意马的控制点置 0。

关键概念

• 先想清 dp[i] 表示“以 i 结尾/走到 i”的什么值；
• 转移来自“更早且已算好的状态”；
• 边界（起点）要单独赋初值。

易错：状态“以 i 结尾”和“前 i 个”容易混；边界漏赋导致答案偏小；下标越界。

练这几道（从易到难）

P1216 Number Triangles（数塔）→ P1115 最大子段和（连续子段）→ P1002 过河卒（路径计数）。

这个模型讲什么

背包 DP 解决“在容量限制下选物品使价值最大”。核心是容量维度的更新顺序。

01 背包（P1048 采药，每件最多一次）：

int dp[V+1] = {0};
for (int i = 1; i <= n; i++)
    for (int j = V; j >= w[i]; j--)            // ⭐ 倒序，保证每件最多用一次
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

完全背包（P1616 疯狂的采药，每件无限）：只把内层循环改成正序 for j=w..V，dp[j-w] 用的就是已含本品的旧值，于是可重复选。

背包方案数（P1164 小 A 点菜）：dp[j] 表示凑出价格 j 的方案数，转移 dp[j] += dp[j-w[i]]，初始 dp[0]=1。

依赖背包（P1064 金明的预算方案）：主件 + 附件捆绑，把“可选组合”预处理成若干物品再做 01 背包。

关键概念

• 01 倒序、完全正序：这一行顺序决定“能否重复选”；
• 一维 dp[j] 复用，省去物品维；
• 方案数用 += 且 dp[0]=1 起步。

易错：01 背包写成正序变成完全背包；方案数忘记 dp[0]=1；容量维数组开小越界。

练这几道（从易到难）

P1048 采药（01 背包）→ P1616 疯狂的采药（完全背包）→ P1164 小 A 点菜（方案数）→ P1064 金明的预算方案（依赖背包）。

这个模型讲什么

区间 / 序列 DP 处理“合并相邻”或“在序列上取最长结构”的问题，状态通常是 dp[l][r]（区间）或 dp[i]（以 i 结尾的序列）。

最长上升子序列 LIS（合唱队形 P1091 / 导弹拦截 P1020）：dp[i] = 以 i 结尾的 LIS 长度。

for (int i = 1; i <= n; i++) {
    dp[i] = 1;
    for (int j = 1; j < i; j++)
        if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);   // 接在更小的后面
}

石子合并（P1880 / P1775，区间 DP）：dp[l][r] = 合并区间 [l,r] 的最小代价，枚举断点 k。

for (int len = 2; len <= n; len++)            // ⭐ 先枚举区间长度
    for (int l = 1; l + len - 1 <= n; l++) {
        int r = l + len - 1; dp[l][r] = INF;
        for (int k = l; k < r; k++)
            dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r] + sum(l,r));
    }

关键概念

• 区间 DP 必须先枚举长度再枚举左端点，保证子区间已算；
• LIS 的 O(n²) 写法足够普及组，进阶有 O(n log n)（贪心 + 二分）；
• 导弹拦截的最长不升子序列长度 = 最少拦截系统数（Dilworth 定理）。

易错：区间 DP 枚举顺序错（先 l 后 len）会用未算的子区间；LIS 把 < 写成 <= 变成非降。

练这几道（从易到难）

P1091 合唱队形（LIS）→ P1020 导弹拦截（LIS/ Dilworth）→ P1775 石子合并弱化（区间 DP 入门）→ P1880 石子合并（区间 DP）。

这个模型讲什么

树形 DP 在树上做 DP：状态定义在“以 u 为根的子树”上，用后序 DFS（先递归儿子，再合并）计算。

没有上司的舞会（P1352）：每个点选/不选，选了父亲就不能选儿子。

int f[N][2];   // f[u][0]=不选u的最大值, f[u][1]=选u的最大值
void dfs(int u, int fa) {
    f[u][1] = happy[u];
    for (int v : son[u]) {
        if (v == fa) continue;
        dfs(v, u);
        f[u][0] += max(f[v][0], f[v][1]);        // 不选 u：儿子可选可不选，取大
        f[u][1] += f[v][0];                      // 选 u：儿子不能选
    }
}

选课（P2014）：树形依赖背包，选了课要先选它的先修课，在树上做分组背包。

滑雪（P1434）：记忆化 DP 求“从高往低滑”的最长路径，dp[u] = 1 + max(dp[v])（v 比 u 低）。

关键概念

• 后序：先 dfs(v) 再合并 f[u]，满足“儿子状态先就绪”；
• 状态常带“选/不选”或“以 u 为根”的维度；
• 多叉树可用 vector 邻接表，DFS 自然递归。

易错：先合并后递归（儿子状态空）；父子约束（选父不能选子）写反；记忆化忘了存 dp[u] 导致重复算。

练这几道（从易到难）

P1352 没有上司的舞会（选/不选）→ P1434 滑雪（记忆化）→ P2014 选课（树形依赖背包）。