第 33 章 DP进阶 · 知识细节练习

DP 三要素是？

判断题：DP 要求问题具有最优子结构——大问题的最优解包含子问题的最优解。

判断题：无后效性不是 DP 的前提——有后效性的问题也能直接递推求解。

状态设计的原则是？

转移设计的原则是？

DP 进阶总表是？

最长上升子序列（LIS）的定义是？

LIS 的 $O(n^2)$ 转移是？

判断题：$O(n^2)$ 的 LIS 逐个枚举每个 $i$ 前面的 $j$——$n=10^5$ 时约 $10^{10}$ 次，必须优化。

判断题：LIS 二分优化（$O(n \log n)$）维护一个"最小结尾数组"tail，用 lower_bound 找到第一个 $\ge a[i]$ 的位置替换——tail 的长度即答案。

判断题：LIS 变体——最长不下降子序列（用 upper_bound）、先离散化、配合树状数组求方案数——核心思想都是"最小结尾"。

LCS（最长公共子序列）的转移是？

判断题：最大子段和——$dp[i]=\max(a[i],\ dp[i-1]+a[i])$，答案取 $\max dp[i]$；全负数组答案为最大单元素。

01 背包（每件物品选 0/1 次）的转移是？

完全背包（每件物品无限次）与 01 背包的区别是？

判断题：多重背包（每件物品有 $c_i$ 件）用二进制拆分——把 $c$ 拆成 $1,2,4,\dots,2^k,r$ 件打包，转成 01 背包，复杂度从 $O(nW\cdot c)$ 降到 $O(nW \log c)$。

判断题：分组背包——每组最多选一件，转移时对每件物品做 01 式决策，容量循环仍在外层。

判断题：依赖背包（选子件必须先选主件）——先处理主件分组，组内做类似 01/分组决策。

判断题：混合背包——把 01 与完全分两类处理（01 逆序、完全正序），循环方向对就不会错。

判断题：背包用一维数组就是"滚动数组"思想——只保留上一阶段结果，空间 $O(W)$；二维压缩一维时注意循环方向。

区间 DP 的核心思想是？

石子合并（相邻合并、代价为两堆和）的转移是？

判断题：环形问题（环形石子合并）→ 断环成链：数组复制一倍（$a[1..n]$ 接 $a[1..n]$），枚举所有长度为 $n$ 的窗口取最优。

判断题：区间 DP 必须按区间长度从小到大枚举（外层 len）——保证用到的子区间都已算好。

判断题：括号序列类区间 DP——$dp[i][j]$ 表示区间内最少添加/匹配数，枚举分割点或首尾配对。

判断题：最长回文子序列（区间 DP）——首尾相等则 $dp[i][j]=dp[i+1][j-1]+2$，否则取两端子区间的 max。

判断题：四边形不等式优化适用于所有区间 DP，任何 $O(n^3)$ 区间 DP 都能优化到 $O(n^2)$。

树上 DP 的核心做法是？

树的直径（最长两点路径）的 DP 求法是？

判断题：树的重心 = 删去后最大连通块最小的点——DP 求每个点子树大小 $sz$，再与 $n-sz$ 取 max 比较。

判断题：树上最大独立集——$dp[u][0]$（不选 u）取儿子选不选的 max 之和，$dp[u][1]$（选 u）取儿子不选之和。

判断题：树上背包——在 DFS 序/子树合并中做容量维 DP，$O(nW)$ 或 $O(n^2)$，是分组背包的树上版。

判断题：换根 DP——先以 1 为根算一遍，再沿边"把根换过去"，$O(n)$ 求所有点为根的答案。

状压 DP 的状态定义是？

状压常用位运算是？

判断题：枚举 mask 的所有子集可用 for (sub = mask; sub; sub = (sub-1) & mask)——总复杂度 $O(3^n)$。

判断题：旅行商问题（TSP）状压 DP——$dp[mask][i]$ 表示走过集合 mask、当前在点 i 的最小代价，逐点扩展；$n\le 20$ 量级可用。

判断题：轮廓线 DP（插头 DP 雏形）——逐格处理棋盘类问题，状态只记录"当前轮廓线"上的信息。

判断题：适用判断——元素个数 $n \le 20$ 左右、状态天然是"选/不选"集合时，考虑状压 DP。

判断题：滚动数组——转移只依赖上一行/上一阶段时，用 i&1（或交换指针）交替使用两行，空间降一维。

判断题：记忆化搜索 = 递归 + 查表——把"算过的状态"存下来，状态图是无环图（或按拓扑序）时等价于 DP。

判断题：单调队列优化——形如 $dp[i] = \max(dp[i-k..i-1]) + a[i]$ 的滑动窗口最值转移，用单调队列 $O(1)$ 取窗口最值。

判断题：斜率优化是 $O(n^2)$ 的通用 DP 优化，任何递推都能套用。

判断题：状态压缩——把"是否选/访问过"等布尔信息压进一个整数的二进制位，从而把状态变成下标。

优化选择流程是？

判断题：初值设置——求 min 的 DP 初始化 INF、求 max 初始化 -INF/0，起点状态单独赋值；初值错全盘错。

判断题：循环顺序——01 背包逆序、完全背包正序、区间 DP 按长度、树形 DP 后序；顺序错结果错。

判断题：空间溢出——$dp[5001][5001]$ 的 int 数组约 100MB（5001²×4B），接近常见内存上限，注意用滚动数组或小类型。

判断题：环形处理——环形序列问题复制一倍断环成链，注意答案取"所有长度为 n 的窗口"而非固定一段。

判断题：以下结论全部正确——"LIS 二分优化 $O(n \log n)$；01 逆序、完全正序；区间 DP 按长度枚举；树形 DP 后序合并；状压只适合 n 很小；滚动数组只留必要维度"。

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 8;
05    int a[9] = {0, 3, 1, 4, 1, 5, 9, 2, 6};   // 下标 1 起
06    int dp[9];
07    for (int i = 1; i <= n; i++) {
08        dp[i] = 1;
09        for (int j = 1; j < i; j++)
10            if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);
11    }
12    int ans = 0;
13    for (int i = 1; i <= n; i++) ans = max(ans, dp[i]);
14    cout << ans;
15    return 0;
16}

单选题：程序输出是？（LIS 长度）

01// 代码与 I1 完全相同，最后输出 dp 数组：
02for (int i = 1; i <= n; i++) cout << dp[i] << " ";

单选题：程序输出是？（以 i 结尾的 LIS 长度）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 8;
05    int a[9] = {0, 3, 1, 4, 1, 5, 9, 2, 6};
06    vector<int> tail;                    // 最小结尾数组
07    for (int i = 1; i <= n; i++) {
08        auto it = lower_bound(tail.begin(), tail.end(), a[i]);
09        if (it == tail.end()) tail.push_back(a[i]);
10        else *it = a[i];
11    }
12    cout << tail.size();
13    return 0;
14}

单选题：程序输出是？

01// 代码与 I3 完全相同，最后输出 tail 数组（注意：tail 不是真正的 LIS）：
02for (int x : tail) cout << x << " ";

单选题：程序输出是？

01for (int i = 1; i <= n; i++) {
02    dp[i] = 1;
03    for (int j = 1; j < i; j++)
04        if (a[j] < a[i]) dp[i] = max(dp[i], ______);   // 接在 j 后面
05}

单选题：横线处应填入？

// 数组换成 {0, 5, 1, 6, 2, 7, 3}（n = 6，下标 1 起），O(n²) 求 LIS

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int W = 7;
05    int w[4] = {0, 2, 3, 4};     // 3 件物品的重量
06    int v[4] = {0, 3, 4, 5};     // 价值
07    int f[8] = {0};
08    for (int i = 1; i <= 3; i++)
09        for (int j = W; j >= w[i]; j--)
10            f[j] = max(f[j], f[j - w[i]] + v[i]);
11    cout << f[W];
12    return 0;
13}

单选题：程序输出是？（最大价值）

01// 代码与 J1 完全相同，最后输出 f[0..7]：
02for (int j = 0; j <= W; j++) cout << f[j] << " ";

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int W = 7;
05    int w[3] = {0, 2, 3};
06    int v[3] = {0, 3, 4};
07    int f[8] = {0};
08    for (int i = 1; i <= 2; i++)
09        for (int j = w[i]; j <= W; j++)       // 正序
10            f[j] = max(f[j], f[j - w[i]] + v[i]);
11    cout << f[W];
12    return 0;
13}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int w = 2, v = 3, c = 4;             // 重量 2、价值 3、共 4 件
05    vector<pair<int,int>> items;
06    for (int k = 1; c > 0; k *= 2) {
07        int t = min(k, c);
08        items.push_back({w * t, v * t}); // 打包 t 件
09        c -= t;
10    }
11    cout << items.size() << " ";
12    for (auto [ww, vv] : items) cout << ww << " " << vv << " ";
13    return 0;
14}

单选题：程序输出是？（拆成的包数与每包的重量价值）

01for (int i = 1; i <= n; i++)
02    for (int j = W; ______; j--)        // 01 背包容量逆序
03        f[j] = max(f[j], f[j - w[i]] + v[i]);

单选题：横线处应填入？

// 一件 01 物品（重量 2 价值 3）+ 一件完全物品（重量 3 价值 4），容量 6
// 先处理 01（逆序），再处理完全（正序），输出 f[6]

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 3;
05    int a[4] = {0, 4, 5, 3};
06    int s[4] = {0};
07    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
08    int dp[4][4];
09    memset(dp, 0x3f, sizeof dp);
10    for (int i = 1; i <= n; i++) dp[i][i] = 0;
11    for (int len = 2; len <= n; len++)
12        for (int i = 1; i + len - 1 <= n; i++) {
13            int j = i + len - 1;
14            for (int k = i; k < j; k++)
15                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + s[j] - s[i - 1]);
16        }
17    cout << dp[1][n];
18    return 0;
19}

单选题：程序输出是？（合并最小代价）

// 图与 K1 完全相同，最后输出：
cout << dp[1][2] << " " << dp[2][3];

单选题：程序输出是？（相邻两堆的合并代价）

// 环形石子：{4,5,3} 首尾相接。断环成链：复制一倍 {4,5,3,4,5,3}
// 对每个长度为 3 的窗口 [i, i+2] 跑石子合并，取最小值
// 窗口 [3,5] = {3,4,5}：(3+4)=7，(7+5)=12，总代价 19

单选题：程序输出是？（环形合并最小代价）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 5;
05    int a[6] = {0, 1, 2, 2, 1, 3};
06    int dp[6][6] = {0};
07    for (int i = 1; i <= n; i++) dp[i][i] = 1;
08    for (int len = 2; len <= n; len++)
09        for (int i = 1; i + len - 1 <= n; i++) {
10            int j = i + len - 1;
11            if (a[i] == a[j]) dp[i][j] = dp[i + 1][j - 1] + 2;
12            else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
13        }
14    cout << dp[1][n];
15    return 0;
16}

单选题：程序输出是？（最长回文子序列长度）

01for (int k = i; k < j; k++)
02    dp[i][j] = min(dp[i][j], dp[i][k] + ______ + s[j] - s[i - 1]);

单选题：横线处应填入？

01for (int len = 2; len <= n; len++) {
02    cout << len << " ";
03    for (int i = 1; i + len - 1 <= n; i++) {
04        int j = i + len - 1;
05        for (int k = i; k < j; k++)
06            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + s[j] - s[i - 1]);
07    }
08}
09// n = 3 时，外层循环输出：

单选题：程序输出是？（len 的取值序列）

// 石子 {1,3,5,2}（n = 4），标准石子合并，输出 dp[1][4]

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03vector<int> g[7];
04int ans = 0;
05int dfs(int u, int fa) {
06    int d1 = 0, d2 = 0;               // 子树中最长链与次长链（不同子树）
07    for (int v : g[u]) {
08        if (v == fa) continue;
09        int d = dfs(v, u) + 1;
10        if (d > d1) { d2 = d1; d1 = d; }
11        else if (d > d2) d2 = d;
12    }
13    ans = max(ans, d1 + d2);
14    return d1;
15}
16int main() {
17    int e[5][2] = {{1,2}, {1,3}, {2,4}, {2,5}, {3,6}};   // 6 个点 5 条边
18    for (auto [u, v] : e) { g[u].push_back(v); g[v].push_back(u); }
19    dfs(1, 0);
20    cout << ans;
21    return 0;
22}

单选题：程序输出是？（树的直径）

// 树同 L1（6 个点）。树上最大独立集：
// dp[u][0] = 不选 u：儿子选不选取 max 之和
// dp[u][1] = 选 u：儿子都不选之和

单选题：程序输出是？（最大独立集大小）

// 树：1-2、2-3、2-4、2-5（5 个点）
// sz[u] = 子树大小；删掉点 u 后最大连通块 = max(各儿子 sz, n - sz[u])
// 重心 = 最大连通块最小的点

单选题：程序输出是？（重心编号与最大连通块大小）

// 依赖背包：树为链 1-2-3，选节点必须已选父节点；价值 v = {1, 2, 3}
// 最多选 m = 2 个节点，求最大价值
// 合法选法：{} = 0、{1} = 1、{1,2} = 3（{2}、{3}、{2,3} 不合法）

单选题：程序输出是？

01int dfs(int u, int fa) {
02    int d1 = 0, d2 = 0;
03    for (int v : g[u]) {
04        if (v == fa) continue;
05        int d = dfs(v, u) + 1;
06        if (d > d1) { d2 = d1; d1 = d; }
07        else if (d > d2) d2 = d;
08    }
09    ans = max(ans, ______);   // 两条链穿过 u 拼接
10    return d1;
11}

单选题：横线处应填入？

// 树为链 1-2-3。换根 DP 求每个点到其他所有点的距离和：
// 以 1 为根：dist[1] = 0+1+2 = 3
// 换根到 2：dist[2] = 1+0+1 = 2
// 换根到 3：dist[3] = 2+1+0 = 3

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int mask = 5;                    // 101 = {1, 3}
05    for (int sub = mask; ; sub = (sub - 1) & mask) {
06        cout << sub << " ";
07        if (sub == 0) break;
08    }
09    return 0;
10}

单选题：程序输出是？（mask = 5 的全部子集）

// 4 个城市，完全图距离：d12=2, d13=5, d14=4, d23=1, d24=6, d34=2
// 状压 DP：dp[mask][i] = 走过集合 mask、当前在 i 的最小代价，从城市 1 出发
// dp[1<<0][0] = 0；最后答案 = min(dp[(1<<4)-1][i] + d[i][0])

单选题：程序输出是？（绕一圈回到 1 的最短回路）

// 3 个点的链 1-2-3，点权 {1, 2, 3}，求最大权独立集（不相邻）
// 枚举 0..(1<<3)-1 中合法子集（无相邻位 1）：{}、{1}、{2}、{3}、{1,3}
// 权值和分别为 0、1、2、3、4，最大 4

单选题：程序输出是？

01for (int j = 0; j < n; j++) {
02    if (______) continue;          // j 已在集合中
03    int nmask = mask | (1 << j);
04    dp[nmask][j] = min(dp[nmask][j], dp[mask][i] + d[i][j]);
05}

单选题：横线处应填入？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int x = 13;                      // 1101
05    int cnt = 0;
06    while (x) { cnt += x & 1; x >>= 1; }
07    cout << cnt;
08    return 0;
09}

单选题：程序输出是？（13 的二进制中 1 的个数）

// n = 4 个元素，枚举 0 .. (1<<4)-1 共 16 个集合，统计元素个数 >= 2 的集合数
// 总数 16，空集 1 个、单元素 4 个 → 16 - 1 - 4 = 11

单选题：程序输出是？

// 数组 {3,1,4,1,5,9,2,6}，用 lower_bound 二分求 LIS 长度

单选题：程序输出是？

// 4 件物品：w = {2,3,4,5}, v = {3,4,5,6}，容量 10，标准 01 背包
// f[10] = max(3+4+5 需 2+3+4=9 价值 12, 4+5+6 需 3+4+5=12 超, 3+4+6 需 10 价值 13)

单选题：程序输出是？（最大价值）

// 环形石子 {4,5,3}，断环成链后枚举所有长度为 3 的窗口取最小合并代价

单选题：程序输出是？

// 树同 L1，两次 DFS 求直径：从 1 出发最远点为 4（距离 2），从 4 出发最远点为 6（距离 4）

单选题：程序输出是？

01int full = ______;            // n 个元素全选的全集掩码

单选题：横线处应填入？

// 混合背包：01 物品（2,3）+ 完全物品（3,4），容量 6
// 先 01 逆序再完全正序，输出 f[6]

单选题：程序输出是？

01for (int i = 1; i <= n; i++) {
02    auto it = ①;                      // 第一个 >= a[i] 的位置
03    if (it == tail.end()) tail.push_back(a[i]);
04    else *it = a[i];
05}

单选题：①处应填？

01for (int i = 1; i <= n; i++)
02    for (int j = W; j >= w[i]; j--)
03        f[j] = max(f[j], ①);

单选题：①处应填？

01for (int i = 1; i <= n; i++)
02    for (int j = ①; j <= W; j++)       // 完全背包：正序
03        f[j] = max(f[j], f[j - w[i]] + v[i]);

单选题：①处应填？

01for (int len = 2; len <= n; len++)
02    for (int i = 1; i + len - 1 <= n; i++) {
03        int j = i + len - 1;
04        for (int k = i; k < j; k++)
05            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + ①);
06    }

单选题：①处应填？（合并两堆的代价）

01// 树上最大独立集
02dp[u][1] = 1;
03for (int v : g[u]) {
04    if (v == fa) continue;
05    dfs(v, u);
06    dp[u][0] += max(dp[v][0], dp[v][1]);
07    dp[u][1] += ①;                    // 选了 u，儿子都不能选
08}

单选题：①处应填？

01for (int mask = 0; mask < (1 << n); mask++)
02    for (int i = 0; i < n; i++)
03        if (dp[mask][i] == INF) continue;
04        else {
05            for (int j = 0; j < n; j++) {
06                if (①) continue;              // j 已访问过
07                int nmask = mask | (1 << j);
08                dp[nmask][j] = min(dp[nmask][j], dp[mask][i] + d[i][j]);
09            }
10        }

单选题：①处应填？

01for (int i = 1; i <= n; i++) {
02    int cur = ①, pre = cur ^ 1;      // 交替两行
03    for (int j = 1; j <= m; j++)
04        dp[cur][j] = max(dp[pre][j], dp[pre][j - w[i]] + v[i]);
05}

单选题：①处应填？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int W = 4;
05    int w[2] = {0, 2}, v[2] = {0, 3};   // 只有一件物品
06    int f[5] = {0};
07    for (int i = 1; i <= 1; i++)
08        for (int j = w[i]; j <= W; j++)     // 注意：写成了正序
09            f[j] = max(f[j], f[j - w[i]] + v[i]);
10    cout << f[W];
11    return 0;
12}

单选题：程序输出是？（01 背包正确结果应为 3）

01// 石子 {4,5,3}，但循环写成了 i 在外层、j 在内层（未按长度枚举）：
02for (int i = 1; i <= n; i++)
03    for (int j = i + 1; j <= n; j++)
04        for (int k = i; k < j; k++)
05            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + s[j] - s[i - 1]);
06// 求 dp[1][3] 时 dp[2][3] 还没算（仍为 INF），只有 k=2 的分支有效：9 + 0 + 12 = 21

单选题：程序输出是？（正确结果应为 20）

01// 完全背包（物品无限），但写成了逆序：
02int W = 4;
03int w[2] = {0, 2}, v[2] = {0, 3};
04int f[5] = {0};
05for (int i = 1; i <= 1; i++)
06    for (int j = W; j >= w[i]; j--)     // 注意：写成了逆序
07        f[j] = max(f[j], f[j - w[i]] + v[i]);
08cout << f[W];

单选题：程序输出是？（完全背包正确结果应为 6——用两次）

01// 石子 {4,5,3}，转移漏掉了 + s[j] - s[i-1]：
02for (int k = i; k < j; k++)
03    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);   // 注意：忘加两堆和

单选题：程序输出是？（正确结果应为 20）

01// 树同 L1，DFS 只返回最长链 d1，但漏掉了 ans = max(ans, d1 + d2);
02int dfs(int u, int fa) {
03    int d1 = 0, d2 = 0;
04    for (int v : g[u]) {
05        if (v == fa) continue;
06        int d = dfs(v, u) + 1;
07        if (d > d1) { d2 = d1; d1 = d; }
08        else if (d > d2) d2 = d;
09    }
10    // 注意：漏掉了 ans 的更新
11    return d1;
12}
13// 最后输出 ans（因漏更新始终为 0）

单选题：程序输出是？（正确直径应为 4）

判断题：以下五种易错写法都会导致程序出错——①01 背包写成正序（物品被重复使用）②区间 DP 不按长度枚举（用到的子区间还没算）③完全背包写成逆序（物品只能用一次）④石子合并忘加两堆和（代价少算）⑤树形 DP 直径忘更新 ans（答案始终为 0）。