适用对象： 完成第 4 课（前缀和与差分）的同学 使用方式： 自学讲义，Dev-C++ 5.11，练习按考场 freopen 格式写 学完本课，你应该能：
先别被"动态规划"这个名字吓到——上节课你已经写过 DP 了：
preSum[i] = preSum[i - 1] + a[i]这行代码干的事情就是：preSum[i]（前 i
个数的和）这个答案，是靠 preSum[i-1]（前 i-1
个数的和）这个更小规模的答案加一个数得来的，算完存进数组里，后面直接查。这就是
DP 的全部套路。
DP 三件套（考场上先在草稿纸上把这三条用中文写清楚，再动手写代码）：
| 三件套 | 要回答的问题 | 前缀和的例子 |
|---|---|---|
| ① 状态定义 | f[i] 到底表示什么？用一句中文说清楚 |
preSum[i] 表示前 i 个数的和 |
| ② 转移方程 | f[i] 怎么由更小的 f[...] 算出来？ |
preSum[i] = preSum[i-1] + a[i] |
| ③ 初始状态 | 最小的那个 f 等于几？边界怎么定？ |
preSum[0] = 0 |
最小的完整例子——爬楼梯： 一次能上 1 级或 2 级台阶，上 n 级台阶共有多少种走法？
f[i] 表示走到第 i 级台阶的方案数f[i] = f[i-1] + f[i-2]f[1] = 1（只有一种走法），f[2] = 2（1+1
或 2）#include <bits/stdc++.h>
using namespace std;
long long f[55];
int main() {
int n = 10;
f[1] = 1;
f[2] = 2;
for (int i = 3; i <= n; i++) f[i] = f[i - 1] + f[i - 2];
cout << f[n] << endl;
return 0;
}输出：89
⚠️ 状态定义说不清楚，转移方程一定写不对。
如果你觉得"这题不知道怎么转移"，十有八九是状态没定义好，回头重新想"f[i]
到底表示什么"，而不是死盯着方程改。
📝 DP 和暴力搜索的区别： 暴力会把同一个小问题反复算很多遍（爬楼梯裸递归是 O(2ⁿ)），DP 把每个小问题的答案算一次就存下来，所以是 O(n)。"存下来别重算"就是 DP 省时间的全部秘密。
题意： 给一个 r 行的数字三角形，从顶点出发，每一步只能走到"左下"或"右下"相邻的数，一直走到底层。求路径上所有数之和的最大值。
样例（洛谷 P1216 官方样例）：
输入样例：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出样例：
30先说一个陷阱：这题不能贪心。
如果每一步都选眼前较大的那个数：7 → 8 → 1 → 7 → 5，总和是
28；而真正的最优路径是 7 → 3 → 8 → 7 → 5，总和
30——第二步故意选了小的
3，才换来后面的大数。上节课（L02）讲贪心时说过：只有"每一步的局部最优不会挡住后面"的题才能贪心，这题恰恰不满足。
DP 三件套：
f[i][j] 表示从第 i 行第 j
列出发，走到底层能拿到的最大和(i, j) 只能走到 (i+1, j) 或
(i+1, j+1)，所以
f[i][j] = a[i][j] + max(f[i+1][j], f[i+1][j+1])f[r][j] = a[r][j]注意这题是自底向上算的（从最后一行往上推），答案就是
f[1][1]。
#include <bits/stdc++.h>
using namespace std;
int a[1005][1005], f[1005][1005];
int main() {
freopen("triangle.in", "r", stdin);
freopen("triangle.out", "w", stdout);
int r;
cin >> r;
for (int i = 1; i <= r; i++)
for (int j = 1; j <= i; j++) cin >> a[i][j];
for (int j = 1; j <= r; j++) f[r][j] = a[r][j]; // ③ 初始状态：最底层
for (int i = r - 1; i >= 1; i--) // 从倒数第二行往上推
for (int j = 1; j <= i; j++)
f[i][j] = a[i][j] + max(f[i + 1][j], f[i + 1][j + 1]);
cout << f[1][1] << endl;
return 0;
}📝 为什么自底向上比自顶向下省事？ 自底向上时"底层的答案"是白送的（就是它自己），不用特判；如果反过来定义成"从顶走到 (i,j) 的最大和"，也能做，但要处理每行第一个和最后一个位置没有左上/右上的边界情况，代码更啰嗦。状态定义换个方向，代码难度能差一倍——这是 DP 最值得练的手感。
题意： 山洞里有 M 株草药，第 i 株需要花
t[i] 分钟采摘，价值 v[i]。总共只有 T
分钟。每株草药要么采、要么不采，不能采一半，也不能采两次。求能拿到的最大总价值。
样例（洛谷 P1048 官方样例）：
输入样例：
70 3
71 100
69 1
1 2
输出样例：
3（第 1 株要 71 分钟，超过总时间 70，采不了；剩下两株时间 69 + 1 = 70 刚好够，价值 1 + 2 = 3。）
这就是最经典的 01 背包——"01"指的是每件物品只有"取（1）"和"不取（0）"两种选择。
f[i][j] 表示只考虑前 i
株草药、总时间不超过 j 分钟时的最大价值f[i][j] = f[i-1][j]j >= t[i]）：f[i][j] = f[i-1][j - t[i]] + v[i]f[i][j] = max(f[i-1][j], f[i-1][j - t[i]] + v[i])f[0][j] = 0（一株都不考虑时，价值是
0）；全局数组自动是 0，不用手写#include <bits/stdc++.h>
using namespace std;
int t[105], v[105];
int f[105][1005];
int main() {
int T = 70, M = 3; // 直接用官方样例的数据，方便你跟着跑
int tt[4] = {0, 71, 69, 1};
int vv[4] = {0, 100, 1, 2};
for (int i = 1; i <= M; i++) { t[i] = tt[i]; v[i] = vv[i]; }
for (int i = 1; i <= M; i++) {
for (int j = 0; j <= T; j++) {
f[i][j] = f[i - 1][j]; // 不采第 i 株
if (j >= t[i])
f[i][j] = max(f[i][j], f[i - 1][j - t[i]] + v[i]); // 采第 i 株
}
}
cout << f[M][T] << endl;
return 0;
}输出：3
注意转移方程里 f[i][...] 只用到了
f[i-1][...]，上上一行根本不需要——那就干脆只留一行，原地更新：
for (int i = 1; i <= M; i++)
for (int j = T; j >= t[i]; j--) // ⚠️ 注意 j 是倒着走的
f[j] = max(f[j], f[j - t[i]] + v[i]);⚠️ 一维 01 背包的内层循环必须倒序，这是本课最重要的一条规矩。
为什么？ 手工走两步就明白了。假设当前处理第 i
株草药，t[i] = 1, v[i] = 2：
j = 70 → 1：算 f[70]
时用到的 f[69] 还没被第 i
株更新过，它代表的是"前 i-1 株的答案"，符合方程要求 → 第 i
株只会被采一次 ✅j = 1 → 70：算 f[2]
时用到的 f[1] 刚刚被第 i 株更新过，于是第
i 株被采了第二次；算 f[3] 时又采第三次……结果这株 1
分钟的草药被采了 70 遍 ❌拿官方样例试：正确答案是 3，把内层写成正序会输出 140（把那株"1 分钟换 2 价值"的草药重复采了 70 次），而且编译器完全不会报错——这种"跑得通但答案偏大"的错误最难查，必须靠记规矩来防。
📝 一句话记法：01 背包（每件只能拿一次）内层倒序；完全背包（每件能拿无限次）内层正序——后者以后学，但你现在已经知道正序会发生什么了。
错误 1：一维 01 背包内层写成了正序
for (int i = 1; i <= M; i++)
for (int j = t[i]; j <= T; j++) ← 正序！
f[j] = max(f[j], f[j - t[i]] + v[i]);
// 编译通过、运行不崩，答案却偏大——每件物品被重复选了很多次📝 写完一维背包，第一件事就是回头确认内层是
for (int j = T; j >= t[i]; j--)。
错误 2：忘了写初始状态
// 漏掉了这一行： for (int j = 1; j <= r; j++) f[r][j] = a[r][j];
for (int i = r - 1; i >= 1; i--)
for (int j = 1; j <= i; j++)
f[i][j] = a[i][j] + max(f[i + 1][j], f[i + 1][j + 1]);f[r][...] 全是
0，等于把最后一行的数字全都白白丢掉了。拿官方样例试：正确答案
30，漏写初始化会输出 25（正好少了最后一行的那个
5）。
📝 DP 三件套里最容易漏的就是第 ③ 条。
写完转移方程，立刻回头问自己一句："最小的那个状态我赋值了吗？" 另外 DP
数组一律开成全局——全局数组自动清零，局部数组不会（int f[1005];
写在 main 里就全是垃圾值，背包会直接算错）。
错误 3：状态数组开小了
int f[100]; // T 最大是 1000
for (int j = T; j >= t[i]; j--) f[j] = ...; // j 能取到 1000，越界！📝 DP 数组的大小按"状态的最大取值 +
一点余量"来开：背包开 f[T + 5]，数字三角形开
f[r + 5][r + 5]。开之前先回头看题目的数据范围那一段。
⭐ 基础题 1：爬楼梯（文件名 t1.cpp，freopen
stairs.in/stairs.out）
一次能上 1 级或 2 级台阶，求上 n
级台阶的方案数（1 ≤ n ≤ 50）。
输入样例：
10
输出样例：
89⚠️ 这题故意把 n 开到 50，答案是
20365011074——超过 int 的范围（约 21
亿），必须用 long long。自己试一下用
int 会输出什么。
#include <bits/stdc++.h>
using namespace std;
long long f[55];
int main() {
freopen("stairs.in", "r", stdin);
freopen("stairs.out", "w", stdout);
int n;
cin >> n;
f[1] = 1;
f[2] = 2;
for (int i = 3; i <= n; i++) f[i] = f[i - 1] + f[i - 2];
cout << f[n] << endl;
return 0;
}⚠️ 如果 n 可能等于 1，f[2]
虽然被赋了值但不会被输出，没有影响；但要是题目允许
n = 0，就得单独想清楚 f[0]
定义成几。DP 题写完一定要单独检查最小的那几个 n。
⭐⭐ 实战题 2：数字三角形（洛谷 P1216 原题，文件名
t2.cpp，freopen
triangle.in/triangle.out）
题面见上文例题一，1 ≤ r ≤ 1000，每个数在
0 ~ 100 之间。
输入样例：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出样例：
30#include <bits/stdc++.h>
using namespace std;
int a[1005][1005], f[1005][1005];
int main() {
freopen("triangle.in", "r", stdin);
freopen("triangle.out", "w", stdout);
int r;
cin >> r;
for (int i = 1; i <= r; i++)
for (int j = 1; j <= i; j++) cin >> a[i][j];
for (int j = 1; j <= r; j++) f[r][j] = a[r][j];
for (int i = r - 1; i >= 1; i--)
for (int j = 1; j <= i; j++)
f[i][j] = a[i][j] + max(f[i + 1][j], f[i + 1][j + 1]);
cout << f[1][1] << endl;
return 0;
}估一下规模：r = 1000 时三角形有 1000×1001÷2 ≈ 50
万个数，DP 每格 O(1)，总共 5×10⁵ 次运算，随便过。两个
1005 × 1005 的全局 int 数组各约 4 MB、合计 8
MB，在通常 128 MB 的内存限制下够用。
⭐⭐⭐ 冲刺题 3：采药（洛谷 P1048 原题，文件名
t3.cpp，freopen
medic.in/medic.out）
题面见上文例题二，1 ≤ T ≤ 1000，1 ≤ M ≤ 100，每株草药的时间和价值都在
1 ~ 100 之间。要求写一维写法。
输入样例：
70 3
71 100
69 1
1 2
输出样例：
3#include <bits/stdc++.h>
using namespace std;
int t[105], v[105];
int f[1005];
int main() {
freopen("medic.in", "r", stdin);
freopen("medic.out", "w", stdout);
int T, M;
cin >> T >> M;
for (int i = 1; i <= M; i++) cin >> t[i] >> v[i];
for (int i = 1; i <= M; i++)
for (int j = T; j >= t[i]; j--) // 倒序！
f[j] = max(f[j], f[j - t[i]] + v[i]);
cout << f[T] << endl;
return 0;
}复杂度 O(M × T) = 100 × 1000 =
10⁵，毫无压力。写完检查三件事：内层倒序了吗？f
是全局数组（自动清零）吗？f 开到 T + 5
了吗？
DP 三件套（草稿纸上先用中文写）：
| 内容 | |
|---|---|
| ① 状态定义 | f[...] 表示什么，一句中文说清 |
| ② 转移方程 | f[...] 怎么由更小规模的 f 算出来 |
| ③ 初始状态 | 最小规模的 f 等于几，边界在哪 |
两道题的三件套：
| 题目 | 状态定义 | 转移方程 |
|---|---|---|
| 数字三角形 P1216 | f[i][j] = 从 (i,j) 走到底层的最大和 |
f[i][j] = a[i][j] + max(f[i+1][j], f[i+1][j+1]) |
| 采药 P1048 | f[j] = 时间不超过 j 时的最大价值 |
f[j] = max(f[j], f[j - t[i]] + v[i]) |
01 背包一维模板（背下来）：
for (int i = 1; i <= M; i++)
for (int j = T; j >= t[i]; j--) // 内层必须倒序
f[j] = max(f[j], f[j - t[i]] + v[i]);易错点： 内层正序 →
变成完全背包，答案偏大且不报错；DP
数组一律开全局（自动清零）；数组大小按数据范围开到
最大值 + 5；方案数类的题注意 long long。
以后学： 完全背包、多重背包、最长上升子序列、区间 DP、树形 DP——今天这三件套的思路完全通用，只是状态更复杂。
7→8→1→7→5 这条路举例