第 17 章 动态规划入门 · 知识细节练习

判断题：动态规划（DP）= 把问题拆成子问题、每个子问题只算一次并记录，由小到大组合出答案——适用前提是最优子结构 + 重叠子问题。

判断题：DP 的三要素：状态（f 数组表示什么）、转移（怎么由小状态算出大状态）、初始化（最小状态的初值）。

判断题：初始化错误会让整张 DP 表错——例如"恰好装满"的背包没有把"不可达容量"设成 $-∞$，就会把非法状态当合法。

判断题：贪心每步只做一个选择；DP 尝试所有转移取最优——DP 更"全面"，但要求状态能编号、转移满足无后效性。

判断题：递推是 DP 的雏形：DP 的"状态 + 转移"就是递推的"数组 + 公式"，DP 多了"取 max/min 的最优决策"。

判断题：做 DP 的标准四步：① 定义状态 ② 写转移方程 ③ 定初始化 ④ 找答案位置。

单选题：爬楼梯 $f(n) = f(n-1) + f(n-2)$，$f(1)=1$、$f(2)=2$。$f(10)$ 的值是？

判断题：最大子段和的一维 DP：f[i] = max(f[i-1] + a[i], a[i])——"接在前一段后面"或"以 a[i] 重新开始"。

单选题：数字三角形自顶向下走（每步左下或右下），第 $i$ 行第 $j$ 列的状态由上一行的哪两个状态转移而来？

判断题：网格从 $(0,0)$ 只能向右/下走到 $(n, m)$，路径数 $f[i][j] = f[i-1][j] + f[i][j-1]$，$f[0][0] = 1$。

判断题：LIS（最长上升子序列）= 从序列中按原顺序选出、不必连续的最长严格递增子序列。

单选题：一排数选若干个数使和最大、且不能选相邻两个，$f[i]$ 表示前 $i$ 个数的最优解，转移是？

判断题：一维 DP 若 $f[i]$ 只依赖 $f[i-1]$、$f[i-2]$，可用滚动变量把空间从 $O(n)$ 降到 $O(1)$。

单选题：01 背包（$N$ 件物品、重量 $w_i$、价值 $v_i$、容量 $C$、每件最多选 1 次），状态 $f[i][j]$ 表示？

单选题：01 背包对第 $i$ 件物品（重量 $w$、价值 $v$）的转移是？

判断题：滚动数组版 01 背包的容量循环必须倒序（j 从 $C$ 到 $w$）——正序会让同一件物品被选多次。

判断题："恰好装满"要求初始化 $f[0]=0$、其余为 $-∞$（或极小值）——装不满的容量状态保持"不可达"。

判断题："不超过容量"（装不满也算合法）时初始化全部为 $0$ 即可。

单选题：求"恰好装满容量 $j$ 的方案数"，滚动数组的转移是？

判断题：01 背包不能用贪心（按单位价值排序会错）——第 15 章的 0/1 背包反例正是 DP 的用武之地。

判断题：二维 DP 的状态是 f[i][j]——"走到/处理到第 $i$ 行第 $j$ 列时……"，常见于网格路径类问题。

判断题：$n imes m$ 矩阵从 $(0,0)$ 到 $(n-1, m-1)$ 只能向右/下走，最大路径和：$f[i][j] = \max(f[i-1][j], f[i][j-1]) + a[i][j]$。

单选题：矩阵路径 DP 中 $f[i][j]$ 由哪两个状态转移而来？

判断题：矩阵路径 DP 中，第一行只能从左方来、第一列只能从上方来——边界行/列的转移要特判，否则会越界读状态。

判断题：有障碍的网格：计数 DP 中障碍格的路径数记为 $0$（不可达），转移时跳过障碍格。

单选题：$n imes m$ 矩阵的二维 DP 时间复杂度是？

判断题：二维 DP 可以逐行滚动：只保留上一行数组，空间从 $O(nm)$ 降到 $O(m)$。

判断题：LIS 要求严格递增（转移条件 $a[j] < a[i]$）；把条件放宽为 $a[j] \leq a[i]$ 就是最长不下降子序列（LNDS）。

单选题：LIS 的 $O(n^2)$ 转移中，$f[i]$ 的初值应是？

单选题：LIS 的长度是？

判断题：记录 pre[i]（$f[i]$ 由哪个 $j$ 转移来），从答案位置沿 pre 倒推，即可还原出一条 LIS。

判断题：子序列不必连续（如 LIS），子段/子数组必须连续（如最大子段和）——两个概念要分清。

判断题：最长长度相同的 LIS 可能有多条（不同元素组成）——题目问方案时注意按规则去重。

判断题：分治的子问题独立不重叠；DP 的子问题大量重叠——这是两者适用场景的分界。

判断题：回溯指数级枚举所有方案；DP 记录每个状态的最优值、避免重复计算——规模大时 DP 是回溯的"高效版"。

判断题：DP 的时间复杂度 = 状态数 × 每个状态的转移代价。

判断题：DP 常见错误：状态定义不清、转移漏分支（如漏"不选"）、初始化错、答案位置取错。

单选题：以下哪类问题不满足最优子结构（子问题最优拼不出全局最优）？

判断题：$n$ 很小时可以用暴力枚举验证 DP 结果（对拍）；$n$ 大时 DP 才是可行方案。

判断题：状态设计三问：状态装得下（数组够大）、转移要简单、答案要取得到。

判断题：转移顺序必须保证"用到的状态先算好"（拓扑序）——背包按容量从小到大、二维 DP 按行从上到下。

判断题：答案可能在 f[n][m]、max(f[n][*]) 或全部状态的最大值——按题目定义取。

判断题：DP 数组要开"状态最大值 + 1"（防止下标越界），越界是 DP 题最常见的崩溃点之一。

单选题：01 背包转移中当 j < w（容量放不下当前物品）时，应该？

判断题：调试 DP 的实用方法：打印整张 DP 表，与小数据手算结果对照，能快速定位状态/转移/初始化错误。

单选题：滚动数组 01 背包把容量循环写成正序，后果是？

单选题："恰好装满"背包却用全 $0$ 初始化，会？

单选题：01 背包转移只写"选"分支、漏了"不选"分支，会？

单选题：LIS 最长子序列不以最后一个元素结尾时，正确做法是？

判断题：以下结论全部正确——"DP 三要素是状态/转移/初始化；01 背包滚动数组容量倒序；LIS 答案取最大值；数字三角形逐行填表"。

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int f[15];
05    f[1] = 1; f[2] = 2;                  // 爬楼梯初始化
06    for (int i = 3; i <= 10; i++)
07        f[i] = f[i - 1] + f[i - 2];      // 转移
08    cout << f[10];
09    return 0;
10}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[6] = {-2, 1, -3, 4, -1, 2};
05    int f[6], best;
06    f[0] = a[0]; best = f[0];
07    for (int i = 1; i < 6; i++) {
08        f[i] = max(f[i - 1] + a[i], a[i]);   // 接上 / 重新开始
09        best = max(best, f[i]);
10    }
11    cout << best;                            // 最大子段和
12    return 0;
13}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[3][3] = {{3, 0, 0}, {1, 5, 0}, {8, 6, 7}};   // 3 层数字三角形
05    int f[3][3] = {0};
06    f[0][0] = a[0][0];
07    for (int i = 1; i < 3; i++)
08        for (int j = 0; j <= i; j++) {
09            f[i][j] = a[i][j];
10            if (j > 0) f[i][j] = max(f[i][j], f[i - 1][j - 1] + a[i][j]);
11            if (j < i) f[i][j] = max(f[i][j], f[i - 1][j] + a[i][j]);
12        }
13    cout << max({f[2][0], f[2][1], f[2][2]});          // 最后一行最大值
14    return 0;
15}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int f[3][3] = {0};                   // 3x3 网格，只能向右/下
05    f[0][0] = 1;
06    for (int i = 0; i < 3; i++)
07        for (int j = 0; j < 3; j++) {
08            if (i > 0) f[i][j] += f[i - 1][j];
09            if (j > 0) f[i][j] += f[i][j - 1];
10        }
11    cout << f[2][2];                     // 从 (0,0) 到 (2,2) 的路径数
12    return 0;
13}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[5] = {3, 2, 5, 10, 7};
05    int f[5];
06    f[0] = a[0];
07    f[1] = max(a[0], a[1]);
08    for (int i = 2; i < 5; i++)
09        f[i] = max(f[i - 1], f[i - 2] + a[i]);   // 不选 / 选（跳过前一个）
10    cout << f[4];
11    return 0;
12}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    long long a = 1, b = 1;              // 滚动变量
05    for (int i = 3; i <= 10; i++) {
06        long long c = a + b;
07        a = b; b = c;
08    }
09    cout << b;
10    return 0;
11}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int cost[6] = {0, 2, 3, 1, 5, 4};   // cost[i]：第 i 级台阶的费用
05    int f[6] = {0};
06    f[1] = cost[1];
07    f[2] = cost[2];
08    for (int i = 3; i <= 5; i++)
09        f[i] = min(f[i - 1], f[i - 2]) + cost[i];   // 从上一级或上上级来
10    cout << f[5];
11    return 0;
12}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[8] = {3, 1, 4, 1, 5, 9, 2, 6};
05    int f[8], ans = 1;
06    for (int i = 0; i < 8; i++) {
07        f[i] = 1;                        // 初值：自己一个
08        for (int j = 0; j < i; j++)
09            if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
10        ans = max(ans, f[i]);
11    }
12    cout << ans;                         // LIS 长度
13    return 0;
14}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[5] = {3, 1, 4, 1, 5};
05    int f[5];
06    for (int i = 0; i < 5; i++) {
07        f[i] = 1;
08        for (int j = 0; j < i; j++)
09            if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
10    }
11    for (int i = 0; i < 5; i++) cout << f[i] << " ";   // 输出每个 f[i]
12    return 0;
13}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[5] = {1, 3, 3, 5, 2};
05    int f[5], ans = 1;
06    for (int i = 0; i < 5; i++) {
07        f[i] = 1;
08        for (int j = 0; j < i; j++)
09            if (a[j] <= a[i]) f[i] = max(f[i], f[j] + 1);   // 不下降：允许相等
10        ans = max(ans, f[i]);
11    }
12    cout << ans;                         // 最长不下降子序列长度
13    return 0;
14}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[6] = {9, 4, 7, 2, 5, 1};
05    int f[6], ans = 1;
06    for (int i = 0; i < 6; i++) {
07        f[i] = 1;
08        for (int j = 0; j < i; j++)
09            if (a[j] > a[i]) f[i] = max(f[i], f[j] + 1);   // 严格下降
10        ans = max(ans, f[i]);
11    }
12    cout << ans;                         // 最长下降子序列长度
13    return 0;
14}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[5] = {2, 1, 5, 3, 4};
05    int f[5], pre[5], ans = 1, pos = 0;
06    for (int i = 0; i < 5; i++) {
07        f[i] = 1; pre[i] = -1;
08        for (int j = 0; j < i; j++)
09            if (a[j] < a[i] && f[j] + 1 > f[i]) { f[i] = f[j] + 1; pre[i] = j; }
10        if (f[i] > ans) { ans = f[i]; pos = i; }
11    }
12    vector<int> seq;                     // 沿 pre 回溯还原 LIS
13    for (int x = pos; x != -1; x = pre[x]) seq.push_back(a[x]);
14    for (int i = seq.size() - 1; i >= 0; i--) cout << seq[i] << " ";
15    return 0;
16}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[5] = {5, 1, 2, 3, 4};
05    int f[5], lis = 1;
06    for (int i = 0; i < 5; i++) {        // LIS：不要求连续
07        f[i] = 1;
08        for (int j = 0; j < i; j++)
09            if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
10        lis = max(lis, f[i]);
11    }
12    int cur = 0, best = 0;               // 最大子段和：必须连续
13    for (int i = 0; i < 5; i++) {
14        cur += a[i];
15        if (cur < 0) cur = 0;
16        best = max(best, cur);
17    }
18    cout << lis << " " << best;
19    return 0;
20}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int w[5] = {0, 2, 3, 4, 5};          // 物品重量（1 下标）
05    int v[5] = {0, 3, 4, 5, 6};          // 物品价值
06    int C = 8, n = 4;
07    int f[10] = {0};                     // 不超过容量，全 0 初始化
08    for (int i = 1; i <= n; i++)
09        for (int j = C; j >= w[i]; j--)  // 容量倒序
10            f[j] = max(f[j], f[j - w[i]] + v[i]);
11    cout << f[C];
12    return 0;
13}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int w[2] = {0, 2};                   // 只有一件物品：重 2 价值 3
05    int v[2] = {0, 3};
06    int C = 6, f[10] = {0};
07    for (int i = 1; i <= 1; i++)
08        for (int j = 0; j <= C; j++)     // 错误：容量正序循环
09            if (j >= w[i]) f[j] = max(f[j], f[j - w[i]] + v[i]);
10    cout << f[C];
11    return 0;
12}

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

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int w[4] = {0, 2, 3, 5};
05    int v[4] = {0, 3, 4, 7};
06    int C = 8, n = 3;
07    int f[10];
08    fill(f, f + 10, -1000000000);        // 恰好装满：其余不可达
09    f[0] = 0;
10    for (int i = 1; i <= n; i++)
11        for (int j = C; j >= w[i]; j--)
12            f[j] = max(f[j], f[j - w[i]] + v[i]);
13    cout << f[C];
14    return 0;
15}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int w[5] = {0, 1, 1, 2, 3};          // 四件物品的重量
05    int C = 4, n = 4;
06    int f[10] = {0};
07    f[0] = 1;                            // 空集：1 种方案
08    for (int i = 1; i <= n; i++)
09        for (int j = C; j >= w[i]; j--)
10            f[j] += f[j - w[i]];         // 方案数用加法
11    cout << f[C];
12    return 0;
13}

单选题：程序输出是？

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

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int w[3] = {0, 2, 3};
05    int v[3] = {0, 3, 4};
06    int C = 5, n = 2;
07    int f[3][10] = {0};                  // 二维表版
08    for (int i = 1; i <= n; i++)
09        for (int j = 0; j <= C; j++) {
10            f[i][j] = f[i - 1][j];       // 不选
11            if (j >= w[i]) f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + v[i]);  // 选
12        }
13    cout << f[n][C];
14    return 0;
15}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int w[3] = {0, 2, 4};
05    int v[3] = {0, 3, 5};
06    int C = 5, n = 2;
07    int f[10];
08    fill(f, f + 10, -1000000000);
09    f[0] = 0;
10    for (int i = 1; i <= n; i++)
11        for (int j = C; j >= w[i]; j--)
12            f[j] = max(f[j], f[j - w[i]] + v[i]);
13    cout << (f[C] < 0 ? -1 : f[C]);      // 恰好装满不可达 → -1
14    return 0;
15}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[3][3] = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};   // 3x3 矩阵
05    int f[3][3] = {0};
06    f[0][0] = a[0][0];
07    for (int i = 0; i < 3; i++)
08        for (int j = 0; j < 3; j++) {
09            if (i == 0 && j == 0) continue;
10            int best = -1e9;
11            if (i > 0) best = max(best, f[i - 1][j]);
12            if (j > 0) best = max(best, f[i][j - 1]);
13            f[i][j] = best + a[i][j];
14        }
15    cout << f[2][2];                 // 最大路径和
16    return 0;
17}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[3][3] = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
05    int f[3][3] = {0};
06    f[0][0] = a[0][0];
07    for (int j = 1; j < 3; j++) f[0][j] = f[0][j - 1] + a[0][j];   // 第一行只能从左来
08    for (int j = 0; j < 3; j++) cout << f[0][j] << " ";
09    return 0;
10}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int g[3][3] = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};   // (1,1) 是障碍
05    int f[3][3] = {0};
06    f[0][0] = 1;
07    for (int i = 0; i < 3; i++)
08        for (int j = 0; j < 3; j++) {
09            if (g[i][j] == 1) { f[i][j] = 0; continue; }   // 障碍格不可达
10            if (i > 0) f[i][j] += f[i - 1][j];
11            if (j > 0) f[i][j] += f[i][j - 1];
12        }
13    cout << f[2][2];                 // 绕过障碍的路径数
14    return 0;
15}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[2][2] = {{2, 3}, {5, 1}};
05    int f[2] = {0};                  // 滚动数组：只保留一行
06    f[0] = a[0][0];
07    f[1] = f[0] + a[0][1];           // 第 0 行
08    for (int j = 0; j < 2; j++) {    // 逐行滚动
09        if (j == 0) f[0] = f[0] + a[1][0];
10        else f[j] = max(f[j], f[j - 1]) + a[1][j];
11    }
12    cout << f[1];                    // 最大路径和
13    return 0;
14}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[3][3] = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
05    int f[3][3] = {0};
06    f[0][0] = a[0][0];
07    for (int i = 0; i < 3; i++)
08        for (int j = 0; j < 3; j++) {
09            if (i == 0 && j == 0) continue;
10            int best = -1e9;
11            if (i > 0) best = max(best, f[i - 1][j]);
12            if (j > 0) best = max(best, f[i][j - 1]);
13            f[i][j] = best + a[i][j];
14        }
15    for (int i = 0; i < 3; i++) {           // 打印整张 DP 表
16        for (int j = 0; j < 3; j++) cout << f[i][j] << " ";
17        cout << endl;
18    }
19    return 0;
20}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[3][3] = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
05    int f[3][3] = {0};
06    f[0][0] = a[0][0];
07    for (int i = 0; i < 3; i++)
08        for (int j = 0; j < 3; j++) {
09            if (i == 0 && j == 0) continue;
10            int best = -1e9;
11            if (i > 0) best = max(best, ______);   // 上方来源
12            if (j > 0) best = max(best, f[i][j - 1]);
13            f[i][j] = best + a[i][j];
14        }
15    cout << f[2][2];
16    return 0;
17}