专题16 · 动态规划1
动态规划最难的不是写代码，而是定义状态。
本讲抓住三件事：状态怎么定、转移怎么写、一维优化时循环方向为什么不能反。
四道题：01 背包、完全背包、最长上升子序列、最长公共子序列。
先判断"这道题能不能用 DP"
① 重叠子问题
同一个子问题被反复计算（如斐波那契 f(5) 里 f(3) 算了很多次）。 → 所以用数组把答案存下来。
② 最优子结构
大问题的最优解由小问题的最优解拼出来。 → 所以可以写"取 max / min"的转移。
③ 无后效性
当前状态一旦确定，以后怎么决策都不会再影响它。 → 所以可以按某个顺序一路填下去。
做一道 DP 题的固定五步
① 定状态（dp[?] 代表什么）→ ② 写转移（怎么从小状态推出来）→
③ 定初值（dp[0]、dp[i][0] 是多少）→ ④ 定顺序（先算谁后算谁）→
⑤ 定答案（最后取哪个格子）。
新手 90% 的错误出在第 ① 步和第 ④ 步。
状态只有一句话：前 i 件、容量 j
状态定义
dp[i][j] = 只考虑前 i 件物品、在容量不超过 j 的限制下，能拿到的最大价值。
答案就是 dp[N][T]。
转移：对第 i 件，只有两种可能
不选 → dp[i][j] = dp[i-1][j]
选（要 j ≥ w[i]）→ dp[i-1][j-w[i]] + v[i]
取两者最大。
for (int i = 1; i <= N; i++)
for (int j = 0; j <= T; j++){
dp[i][j] = dp[i-1][j]; // 不选
if (j >= w[i]) dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i]); // 选
}
一格一格填：看清"选"还是"不选"
为什么 j 必须倒着走
二维降到一维后，dp[j] 要表示"容量 j 的最优值"。
关键是：你读到的 dp[j−w] 到底是哪一轮的？切到「正序（错误写法）」看它怎么把一件物品用了两次。
同一个 dp 数组，换个方向就是另一道题
为什么正序能"重复取"
算 dp[j] 时，dp[j-w] 已经在本轮被更新过，
它可能已经包含了这件物品 → 再加一次就是取了两次、三次……
为什么倒序不能
倒序时 dp[j-w] 还是上一轮（还没考虑过这件物品）的值，
所以这件物品最多只会被加进去一次。
状态是"以 i 结尾"，不是"前 i 个"
状态定义（关键）
d[i] = 以第 i 个数结尾的最长上升子序列长度。
必须"以 i 结尾"，否则转移时不知道最后一个数是谁，无法判断能否接上。
转移与答案
d[i] = max(d[j]) + 1，其中 j < i 且 a[j] < a[i]；
初值 d[i] = 1（至少自己一个）；
答案 = max(d[i])，不是 d[n]！
for (int i = 0; i < n; i++){
d[i] = 1;
for (int j = 0; j < i; j++)
if (a[j] < a[i]) d[i] = max(d[i], d[j] + 1);
}
int ans = 0; for (int i = 0; i < n; i++) ans = max(ans, d[i]);
a[j] >= a[i]（允许相等），第二问用 a[j] < a[i]（严格）。
把 >= 写成 >，样例就从 6 变成 5。看每个位置怎么"接"到前面
二维：两个串的前缀对前缀
状态定义
dp[i][j] = A 的前 i 个字符与 B 的前 j 个字符的 LCS 长度。
答案是 dp[n][m]。
转移（只有两种情况）
若 A[i] == B[j] → dp[i][j] = dp[i-1][j-1] + 1；
否则 → dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
为什么"不等"时是取两个 max
A[i] 和 B[j] 不相等，说明它们不可能同时出现在 LCS 的末尾。
那么最优解要么不用 A[i]（= dp[i-1][j]），要么不用 B[j]（= dp[i][j-1]），
两种都试，取大的。
相等走斜、不等取大
同一组数据：01 得 3，完全得 140
样例：T=70，草药 ①(71,100) ②(69,1) ③(1,2)。 01 背包每株只有一株 → 最优 3；完全背包可以反复采 → 第 ③ 种采 70 株得 140。
两张背包的代码，只差循环方向
01 背包（采药）
int dp[1005];
for (int i = 0; i < M; i++){
int t, v; cin >> t >> v;
for (int j = T; j >= t; j--) // ★ 倒序
dp[j] = max(dp[j], dp[j-t] + v);
}
cout << dp[T];完全背包（疯狂的采药）
long long dp[100005];
for (int i = 0; i < M; i++){
int t; long long v; cin >> t >> v;
for (int j = t; j <= T; j++) // ★ 正序
dp[j] = max(dp[j], dp[j-t] + v);
}
cout << dp[T];① 循环方向写反
01 写成正序 → 变成完全背包，答案偏大； 完全写成倒序 → 变成 01，答案偏小。样例必挂。
② 答案取错位置
LIS 的答案是 max(d[i]) 而不是 d[n]；
背包若容量为"恰好"则要初始化 -INF。
③ 价值溢出
完全背包价值可以很大（70×2=140，N 大时更大），
int 不够 → long long。
DP 是"要么满分、要么零分"——所以先拿保底
复赛一道题 100 分是分好几档给的。会正解当然好， 但不会正解时，前面几档照拿。四道题各拿 30~40 分，加起来就是一等奖和二等奖的分界。
① 特判档：先别想算法，看数据范围表
题目给的数据范围表就是出题人给你的送分清单。看到「n = 1」「只有 1 件物品」这类一行，
就先写个 if 直接输出答案。2 分钟换 5~10 分，全场最划算。
② 暴力档：DFS 枚举所有选法
每件物品「选 / 不选」，n ≤ 20 时 2²⁰ ≈ 100 万，完全跑得完。
先把暴力写对，它既是保底分，又是后面对拍的标尺。
③ 特殊性质档：题目里那句"若……"
常见送分性质：所有物品时间相同（→ 按价值排序贪心）、代价都是 1（→ 退化成计数）、 数据已经有序（→ 不用 DP，直接扫一遍）。
④ 正解档：状态定了，就赢了八成
DP 的时间几乎都花在定义状态上，不是写代码。写完先跑样例， 再用暴力档造小数据对拍——这是唯一能证明你状态定义对的办法。
本讲三道题，各自的四档怎么走
采药 HERB（01 背包）
第1档 · 2 分钟M == 1：时间够就采，不够输出 0。
第2档 · 8 分钟
DFS 每件选/不选，M ≤ 20 稳过。
第3档 · 10 分钟
若所有草药时间相同 → 按价值从大到小取。
第4档 · 15 分钟
一维 dp，容量 倒序。
疯狂的采药 HERB2
第1档 · 2 分钟M == 1：答案就是 (T/t) × v。
第2档 · 8 分钟T ≤ 10000 时，O(T×M) 完全背包直接过。
第3档 · 10 分钟
若所有 t == 1 → 全采价值最大的，T × maxV。
第4档 · 15 分钟
容量 正序 + long long。
导弹拦截 MISSILE
第1档 · 2 分钟n == 1 → 输出 1 / 1。
第2档 · 8 分钟n ≤ 20：枚举所有子序列 2ⁿ。
第3档 · 12 分钟
只做第一问（最长不升，注意是 >=）；
第二问用贪心：每颗导弹放进能拦它的最低那套系统。
第4档 · 15 分钟
两个 LIS，答案取 max(d[i])。
0–5 分钟 读题 + 圈出数据范围表里最小的那几档 → 5–15 分钟 写完第 1、2 档并先交一次（保住 20~30 分）→ 15–40 分钟 冲第 3、4 档 → 40–50 分钟 造小数据对拍、检查
freopen 与文件名。