📌 动态规划进阶
所属等级：GESP 7级 ｜ 难度： ｜ 关键词：状态设计、线性DP、区间DP、最优子结构
📝 考纲要求
- 理解动态规划（DP）的核心思想：最优子结构与无后效性；
- 掌握线性 DP 的状态设计与递推（如最长上升子序列 LIS、最大子段和）；
- 了解区间 DP 的写法（枚举区间长度与起点）；
- 能正确写出状态转移方程并完成填表（数组递推）。
📖 通俗讲解
💡 一句话理解
DP 就是“把大问题拆成小问题，记住每个小问题的答案，避免重复算”。关键是想清楚：dp[i] 代表什么，以及它怎么由更小的 dp 推出来。
① 线性 DP：最长上升子序列（LIS）
问题：给定一个数列，求其中最长的严格递增子序列长度。
🖼️ 图解
二维 dp 表：填 dp[i][j] 时，只依赖 上边 与 左边 已算好的格子
j→ 0 1 2 3
i↓ ┌───┬───┬───┬───┐
0 │ 1 │ 1 │ 1 │ 1 │
├───┼───┼───┼───┤
1 │ 1 │ ● │ ← │ ↑ │
├───┼───┼───┼───┤
2 │ 1 │ ↑ │ │ │
└───┴───┴───┴───┘
● 当前格；← 来自左(dp[i][j-1])；↑ 来自上(dp[i-1][j])
状态转移：dp[i][j] = 更优(上, 左)C++
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1005;
int a[N], dp[N]; // a 原数组，dp[i] 以 a[i] 结尾的 LIS 长度
int n, ans;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
dp[i] = 1; // 至少包含自己，长度初值 1
for (int j = 1; j < i; j++) {
if (a[j] < a[i]) { // 前面有更小的数可接上
dp[i] = max(dp[i], dp[j] + 1);
}
}
ans = max(ans, dp[i]); // 随时更新全局最大值
}
cout << ans << endl;
return 0;
}输入 / 输出6
1 3 2 5 4 6
4
② 区间 DP：石子合并（入门版）
问题：一排石子，每次合并相邻两堆，代价为两堆石子数之和，求合并成一堆的最小总代价（n 较小）。
C++
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 105;
const int INF = 1e9;
int a[N], sum[N]; // a 每堆石子，sum 前缀和
int dp[N][N]; // dp[l][r] 合并 l~r 区间的最小代价
int main() {
int n; cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum[i] = sum[i-1] + a[i]; // 前缀和：区间和 = sum[r]-sum[l-1]
}
// 枚举区间长度 len，从 2 开始（len=1 代价为 0）
for (int len = 2; len <= n; len++) {
for (int l = 1; l + len - 1 <= n; l++) {
int r = l + len - 1;
dp[l][r] = INF;
// 枚举最后在哪处分两堆
for (int k = l; k < r; k++) {
int cost = dp[l][k] + dp[k+1][r] + (sum[r] - sum[l-1]);
dp[l][r] = min(dp[l][r], cost);
}
}
}
cout << dp[1][n] << endl;
return 0;
}输入 / 输出4
1 3 2 4
20
🔵 核心必背重点
✅ 必背
- 四步法：① 定义状态 dp 的含义 ② 想转移方程 ③ 定初值/边界 ④ 确定计算顺序；
- 线性 DP：常见 dp[i] 表示“以 i 结尾/到 i 为止”的最优值；
- 区间 DP：先枚举长度 len，再枚举起点 l，k 切分区间；
- 初值：求最大初始化为 0/-INF，求最小初始化为 INF/0；
- 避免重复计算，用数组把子问题答案存起来。
🔑
记忆口诀：“先想 dp 是什么，再想它从哪来；初值边界别漏掉，计算顺序要排好。”
🔴 考试拉分难点
⚠️ 难点
- 状态设计：题目稍微变化（如“相邻不能取”）就要加维度，例如
dp[i][0/1]表示第 i 个取/不取； - 区间 DP 顺序：必须先算短区间再算长区间（按 len 递增），否则用的还是未知数；
- 初始化陷阱：求 min 时若初值设 0，min 永远取 0；求 max 时若初值太大也会错；
- 答案位置：LIS 答案是
max(dp[i])而非dp[n]（不一定以最后元素结尾）。
🟡 高频易错陷阱
🚫 扣分坑点
- LIS 直接输出
dp[n]而非全局最大值； - 区间 DP 初值没设 INF，或漏了“区间和”这一项代价；
- 数组开太小越界（n 最大要留余量）；
- 用
bits/stdc++.h（禁用），只用iostream/algorithm。
🧪 例题演练
例题 1（基础题）：最大子段和
题目：求一个整数序列中和最大的连续子段（至少取一个）。
C++
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1005;
int a[N], dp[N]; // dp[i] 以第 i 个数结尾的最大子段和
int n, ans;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
// 要么接上前面的子段，要么自己单独开头
dp[i] = max(a[i], dp[i-1] + a[i]);
ans = max(ans, dp[i]); // 记录全局最大
}
cout << ans << endl;
return 0;
}输入 / 输出5
-2 1 -3 4 -1
4
例题 2（模拟真题）：0/1 背包（经典线性 DP）
题目：n 件物品，每件重量 w、价值 v，背包容量 C，每件最多取一次，求能装的最大价值。
C++
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1005;
int dp[N]; // dp[c] 容量 c 下的最大价值（滚动数组）
int n, C;
int main() {
cin >> n >> C;
for (int i = 1; i <= n; i++) {
int w, v; cin >> w >> v;
// 倒序枚举容量：保证每件物品只被用一次
for (int c = C; c >= w; c--) {
dp[c] = max(dp[c], dp[c - w] + v);
}
}
cout << dp[C] << endl;
return 0;
}输入 / 输出3 5
2 3
3 4
4 5
7
🚫 错误示范
for(int c=w;c<=C;c++) dp[c]=max(dp[c],dp[c-w]+v); —— 正序枚举容量会让同一件物品被反复取多次（变成“完全背包”）。0/1 背包必须倒序枚举。
🛡️ 避坑总结
- 先明确定义 dp 状态，再写转移方程；
- LIS / 最大子段和答案是全局 max，不是 dp[n]；
- 区间 DP 按长度递增计算，别用未算好的长区间；
- 0/1 背包容量倒序枚举，完全背包才正序；
- 只用标准库头文件，禁用 bits/stdc++.h。
💡 提示：按 ← → 方向键可在上一 / 下一知识点间快速翻页