动态规划¶

方法速览¶

模板	状态设计	转移要点	辨识信号
0-1 背包	`dp[j]` = 容量 j 的最大价值	物品外层、容量倒序	每件最多一件
完全背包	同上	容量正序	每件无限件
LIS	`dp[i]` = 以 i 结尾的最长上升长度	`dp[i] = max(dp[j])+1`（\(a_j < a_i\)）	“最长上升/不降子序列”
LCS	`dp[i][j]` = 两前缀的公共长度	相等则左上 +1，否则取上/左大	“两个串的公共子序列”

三要素口诀：状态（dp[i] 表示什么）→ 转移（从小状态推大状态）→ 初值（边界 + 不合法态设 \(-\infty/0\)）。

0-1 背包¶

n 件物品各一件，重量 w、价值 v，容量 W 下最大化价值：

for (int i = 1; i <= n; i++)              // 逐件物品
    for (int j = W; j >= w[i]; j--)       // 容量【倒序】！
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

倒序的原因：一维滚动时，dp[j - w[i]] 必须是“没选过物品 i”的旧值；正序会让同一件物品被选两次（那就成完全背包了）。

例：物品 \(\{(w,v)\} = \{(1,1), (3,4), (4,5)\}\)、容量 7：

阶段	dp[0..7]	说明
初始	0 0 0 0 0 0 0 0
物品 1 (w=1,v=1)	0 1 1 1 1 1 1 1
物品 2 (w=3,v=4)	0 1 1 4 5 5 5 5	j=3 起可装
物品 3 (w=4,v=5)	0 1 1 4 5 5 6 9	3+4=7 装满 → 4+5=9

答案 9（选物品 2 + 物品 3 恰好装满）。

完全背包¶

每件物品无限件——只把容量循环改正序：

for (int i = 1; i <= n; i++)
    for (int j = w[i]; j <= W; j++)       // 容量【正序】
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

正序让 dp[j - w[i]] 用上本轮已更新的值——同件物品可以再次被选。

例：物品 \(\{(2,3), (3,4)\}\)、容量 8：物品 1 正序时 dp[4] = dp[2]+3 = 6（两件）… 最终 dp[8] = 12（四件物品 1：\(4\times3\)）。

最长上升子序列 LIS¶

dp[i] = 以 \(a_i\) 结尾（不是前 i 个的最优！）的最长上升长度：

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);
}
ans = *max_element(dp + 1, dp + n + 1);     // 答案取全局 max

例：\(a = \{3, 1, 2, 5, 4\}\)：

i	1	2	3	4	5
\(a_i\)	3	1	2	5	4
dp[i]	1	1	2	3	3

LIS = 3（如 \(1,2,5\) 或 \(1,2,4\)）。注意 dp[5] = 3 而不是 4——4 只能接在比它小的后面。\(O(n^2)\) 是初赛要求版（\(O(n\log n)\) 用二分优化）。

最长公共子序列 LCS¶

dp[i][j] = A 前 i 个与 B 前 j 个的 LCS 长度：

\[dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & a_i = b_j \\ \max(dp[i-1][j],\ dp[i][j-1]) & \text{否则} \end{cases}\]

例：A = ABCBDAB、B = BDCABA 的 dp 表（行为 A 列为 B）：

	B	D	C	A	B	A
""	0	0	0	0	0	0
A	0	0	0	1	1	1
B	1	1	1	1	2	2
C	1	1	2	2	2	2
B	1	1	2	2	3	3
D	1	2	2	2	3	3
A	1	2	2	3	3	4
B	1	2	2	3	4	4

LCS = 4（如 BCBA / BDAB）。“子序列”允许跳选、保序——与子串（连续）不同。

练习题目¶

练习 1 · DP 与贪心的区别¶

题目

动态规划与贪心的本质区别（）

A. 没有区别
B. 贪心总是更准
C. DP 不能用于最优化
D. DP 更慢但能保证全局最优；贪心每步取局部最优，不保证

答案与解析

答案：D

DP 考察所有子状态；贪心只走一条局部最优路——贪心正确性需要证明，DP 天然全局。

练习 2 · 三要素¶

题目

设计动态规划的第一步是（）

A. 写循环
B. 定义状态（dp 数组的含义）
C. 输出答案
D. 开大数组

答案与解析

答案：B

状态定义错，转移与初值全白搭——“dp[i] 表示什么”一句话说不清就别往下写。

练习 3 · 无后效性¶

题目

DP 对状态的要求“无后效性”指（）

A. 不需要初始化
B. 程序没有副作用
C. 之前的决策一旦确定，之后的演化与“如何到达当前状态”无关
D. 数据不能重复

答案与解析

答案：C

未来的转移只看当前状态值，不看路径——这是“状态足够”的标志。

练习 4 · 0-1 背包容量循环方向¶

题目

一维 0-1 背包的容量循环必须（）

A. 正序（从小到大）
B. 任意
C. 倒序（从大到小）
D. 隔一个跳

答案与解析

答案：C

倒序保证 dp[j-w] 是上一轮（未选当前物品）的值；正序会让一件物品被重复选取。

练习 5 · 倒序失效演示¶

题目

0-1 背包（w=2, v=3）、容量 4，若容量循环误写成正序，dp[4] 会变成（）

A. \(3\)（正确：一件）
B. \(6\)（错装两件）
C. \(0\)
D. \(9\)

答案与解析

答案：B

正序时 dp[2]=3 先更新，轮到 j=4 用 dp[2]+3=6——同一件物品被“再选一次”，0-1 变完全。

练习 6 · 完全背包循环方向¶

题目

完全背包（物品无限）的容量循环应（）

A. 倒序
B. 只扫奇数容量
C. 与 0-1 相同
D. 正序

答案与解析

答案：D

正序让转移用到本轮更新过的值，恰好表达“同件可重复选”。

练习 7 · 0-1 背包小例¶

题目

物品 \(\{(w,v)\} = \{(1,1), (3,4), (4,5)\}\)、容量 7 的 0-1 背包最大价值是（）

A. \(10\)
B. \(6\)
C. \(8\)
D. \(9\)

答案与解析

答案：D

选物品 2 + 物品 3（\(3+4=7\) 恰满）：\(4+5=9\)；dp 表演算见教学节。

练习 8 · 装不满与装得下¶

题目

0-1 背包若要求“恰好装满”才计入价值，初始值应设（）

A. 全 0
B. dp[0]=0，其余 \(-\infty\)
C. 全 \(+\infty\)
D. 全 1

答案与解析

答案：B

“恰好装满”时非零容量初始不可达（\(-\infty\) 防止从非法态转移）；“至多装下”（常规背包）才全 0。

练习 9 · 完全背包小例¶

题目

物品 \(\{(2,3), (3,4)\}\)、容量 8 的完全背包最大价值是（）

A. \(12\)
B. \(10\)
C. \(8\)
D. \(11\)

答案与解析

答案：A

四件物品 1（\(w=2\times4=8\)）：\(3\times4 = 12\)；物品 2 组合最多 \(\lfloor 8/3\rfloor=2\) 件 8 或混装 3+3+2 → \(4+4+3 = 11\)，12 更大。

练习 10 · LIS 状态含义¶

题目

LIS 的 dp[i] 标准含义是（）

A. 前 i 个元素的最长上升子序列长度
B. 以 \(a_i\) 结尾的最长上升子序列长度
C. 前 i 个元素的和
D. 第 i 大的元素

答案与解析

答案：B

“以 i 结尾”才能写出转移（只从 \(a_j < a_i\) 的 j 转来）；A 无法直接递推。最终答案是 \(\max_i dp[i]\)。

练习 11 · LIS 手算¶

题目

\(\{3, 1, 2, 5, 4\}\) 的 LIS 长度是（）

A. \(2\)
B. \(4\)
C. \(3\)
D. \(5\)

答案与解析

答案：C

\(1,2,5\)（或 \(1,2,4\)）；dp 依次 1,1,2,3,3。

练习 12 · LIS 末项陷阱¶

题目

接上题数据，dp[5]（以 4 结尾）的值是（）

A. \(4\)
B. \(3\)
C. \(2\)
D. \(1\)

答案与解析

答案：B

比 4 小的元素有 3、1、2，都能接在 4 前面：最优是接 1、2 成 \(1,2,4\)，长 3；不能接 5（\(5 > 4\)）——结尾元素限死了可接的前驱。

练习 13 · 严格上升 vs 不下降¶

题目

“最长不下降子序列”与 LIS 的转移条件差异（）

A. a[j] < a[i] 改成 a[j] <= a[i]
B. 循环方向反过来
C. 初值改 0
D. 没有差异

答案与解析

答案：A

不下降允许相等元素相接；“上升”是严格小于。审题看“上升/不降/不增/下降”四个字眼。

练习 14 · LIS 复杂度¶

题目

标准两重循环 LIS 的时间复杂度是（）

A. \(O(n)\)
B. \(O(n \log n)\)
C. \(O(n^2)\)
D. \(O(n^2\log n)\)

答案与解析

答案：C

i 一层、j < i 一层；\(O(n\log n)\) 版要配合二分/树状数组（超纲了解）。

练习 15 · LIS 最坏输入¶

题目

\(\{5, 4, 3, 2, 1\}\) 的 LIS 长度是（）

A. \(5\)
B. \(1\)
C. \(2\)
D. \(0\)

答案与解析

答案：B

完全递减时任何两个数都不上升，只能选单个。

练习 16 · LIS 最好输入¶

题目

\(\{1, 2, 3, 4, 5\}\) 的 LIS 长度是（）

A. \(5\)
B. \(4\)
C. \(3\)
D. \(2\)

答案与解析

答案：A

整个序列就是答案；dp[i] = i。

练习 17 · LCS 状态¶

题目

LCS 的 dp[i][j] 表示（）

A. A 串的前缀和
B. A 前 i 个与 B 前 j 个的最长公共子串长度
C. 两个串的编辑距离
D. A 前 i 个与 B 前 j 个的最长公共子序列长度

答案与解析

答案：D

子序列允许跳选；子串版（连续）转移在失配时要重置，完全不同。

练习 18 · LCS 转移¶

题目

LCS 转移中 \(a_i \ne b_j\) 时，dp[i][j] 取（）

A. dp[i-1][j-1] + 1
B. dp[i-1][j-1]
C. min(dp[i-1][j], dp[i][j-1])
D. max(dp[i-1][j], dp[i][j-1])

答案与解析

答案：D

失配时丢掉 a 的末位或 b 的末位，两者取大；+1 只属于相等分支。

练习 19 · LCS 小例¶

题目

ABC 与 AC 的 LCS 长度是（）

A. \(3\)
B. \(1\)
C. \(2\)
D. \(0\)

答案与解析

答案：C

公共子序列 AC（A、C 跳过中间的 B 保序）。注意 AC 在 ABC 中不连续，所以它是子序列不是子串——本题问的是子序列。

练习 20 · LCS 无公共字符¶

题目

ABC 与 DEF 的 LCS 长度是（）

A. \(0\)
B. \(1\)
C. \(2\)
D. \(3\)

答案与解析

答案：A

无任何公共字符；dp 表全 0。

练习 21 · LCS 经典值¶

题目

ABCBDAB 与 BDCABA 的 LCS 长度是（）

A. \(3\)
B. \(4\)
C. \(5\)
D. \(2\)

答案与解析

答案：B

如 BCBA；完整 7×6 dp 表见教学节。

练习 22 · LCS 的对称性¶

题目

LCS(A, B) 与 LCS(B, A)（）

A. 相等
B. 前者更大
C. 后者更大
D. 不确定

答案与解析

答案：A

公共子序列的对称定义——dp 表转置即可互推。

练习 23 · 数字三角形¶

题目

从三角形顶走到底，每步走到下一层相邻两格之一，路径和最大。下图最大路径和是（）

```text 7 3 8 8 1 0 2 7 4 4

4 5 2 6 5 ```

- A. $7$
- B. $28$
- C. $25$
- D. $30$

答案与解析

答案：D

自底向上：dp[i][j] = t[i][j] + max(dp[i+1][j], dp[i+1][j+1])，最优路径 7→3→8→7→5 = 30。

练习 24 · 爬楼梯¶

题目

每次上 1 或 2 阶，上 5 阶的方案数是（）

A. \(5\)
B. \(8\)
C. \(16\)
D. \(13\)

答案与解析

答案：B

\(f(n) = f(n-1) + f(n-2)\)（最后一步跨 1 或 2 阶）：1,2,3,5,8——就是斐波那契。

练习 25 · 记忆化搜索¶

题目

“记忆化搜索”与递推的关系（）

A. 记忆化只能用于斐波那契
B. 记忆化更快一个数量级
C. 两者都是 DP 的实现方式，本质等价
D. 递推不能算 DP

答案与解析

答案：C

记忆化 = 递归 + 缓存（自顶向下）；递推 = 循环填表（自底向上）——同一转移方程的两种写法。

练习 26 · 模板辨识¶

题目

“给定点数与边数的 DAG，求从起点到终点的最长路”最像哪个模板的变形？（）

A. LIS（按拓扑序做 dp）
B. LCS
C. 完全背包
D. 二分

答案与解析

答案：A

dp[v] = max(dp[u] + w(u,v)) 沿拓扑序推进——“图上的 LIS 式转移”；关键都在无环保证阶段有序。

易错小结¶

一维背包循环方向是生死线：0-1 倒序、完全正序——写反模型就互变；
LIS 的 dp[i] 是“以 i 结尾”，答案取全局 max；“上升”是严格 <，不下降是 ≤；
LCS 失配取 max(上, 左)、相等才左上 +1；它是子序列不是子串；
“恰好装满”初始化 \(-\infty\)、“至多装下”初始化 0；
DP 与贪心：DP 全局最优、贪心要证明；无后效性是状态合法的标志；
数字三角形自底向上、爬楼梯即斐波那契——小模型先手算 dp 表再答。

	B	D	C	A	B	A
""	0	0	0	0	0	0
A	0	0	0	1	1	1
B	1	1	1	1	2	2
C	1	1	2	2	2	2
B	1	1	2	2	3	3
D	1	2	2	2	3	3
A	1	2	2	3	3	4
B	1	2	2	3	4	4

	B	D	C	A	B	A
""	0	0	0	0	0	0
A	0	0	0	1	1	1
B	1	1	1	1	2	2
C	1	1	2	2	2	2
B	1	1	2	2	3	3
D	1	2	2	2	3	3
A	1	2	2	3	3	4
B	1	2	2	3	4	4

	B	D	C	A	B	A
""	0	0	0	0	0	0
A	0	0	0	1	1	1
B	1	1	1	1	2	2
C	1	1	2	2	2	2
B	1	1	2	2	3	3
D	1	2	2	2	3	3
A	1	2	2	3	3	4
B	1	2	2	3	4	4