15 动态规划入门与经典模型

GESP 6 级CSP-J / NOIP 核心CSP-S

级别标注：GESP 6 级（考级要求）/ CSP-J、NOIP 核心（竞赛进阶：背包、线性、区间、坐标、DAG 图 DP、状态压缩 DP 前置）。

一、动态规划（DP）是什么

动态规划 = 把问题拆成相互重叠的子问题，记录并复用子问题的解，避免重复计算。与分治的区别：分治子问题独立，DP 子问题重叠。

DP 三要素（务必理解）： 1. 状态定义：dp[i] 表示什么（如"前 i 件物品的最大价值"）。 2. 状态转移方程：如何由子状态推出当前状态。 3. 初始条件（边界）：dp[0] 等起点值。

思考顺序：先定义状态 → 推转移 → 设初始 → 编码时用循环填表（或记忆化递归）。

形象理解DP 像记账本式的爬楼梯：想知道第 100 级楼梯有几种走法，不用从第 1 级重新试，只要记住“到第 98 级有几种、到第 99 级有几种”，加起来就行——子问题重叠，答案复用。分治子问题彼此独立，DP 子问题互相重叠，这是本质区别。

考级视角做题四步走：①定义状态 → ②写转移方程 → ③设边界 → ④填表/记忆化。GESP 6 级笔试常考“给转移方程选正确的 dp 定义”，先把 dp[i] 代表什么写清楚再动手。

二、线性 DP：最长上升子序列（LIS）

状态：dp[i] = 以 a[i] 结尾的最长上升子序列长度。

C++ 实例

#include <iostream>
using namespace std;
const int N = 1005;
int a[N], dp[N];         // dp[i]：以 a[i] 结尾的最长上升子序列长度
int main() {
    int n; cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    int ans = 0;
    for (int i = 0; i < n; i++) {
        dp[i] = 1;                       // 子序列只有自己，长度至少 1
        for (int j = 0; j < i; j++) {    // 尝试接在 j 后面
            if (a[j] < a[i]) {           // 满足上升条件
                dp[i] = max(dp[i], dp[j] + 1);  // 接上后长度 +1
            }
        }
        ans = max(ans, dp[i]);           // 全局最优
    }
    cout << ans << endl;
    return 0;
}

复杂度 O(n²)。进阶：贪心 + 二分可优化到 O(n log n)（19 章）。

最大子段和（线性 DP 经典）

C++ 实例

// 最大子段和：滚动一维 dp，空间 O(1)
#include <algorithm>   // 片段自洽：使用 max 需要此头文件
using namespace std;     // 让 max 可直接使用
int maxSubSum(int a[], int n) {
    int dp = 0, best = -1e9;   // dp 表示以当前元素结尾的最大和
    for (int i = 0; i < n; i++) {
        dp = max(a[i], dp + a[i]);   // 要么重新开始，要么接上前一段
        best = max(best, dp);        // 更新全局答案
    }
    return best;
}

形象理解LIS 像给一排身高不同的人排队照相，要求从左到右越来越高，最多能挑几个人。dp[i] 表示“以第 i 个人结尾的最长队”，每个人回头看前面比自己矮的，接在最长的那队后面。

易错点LIS 的 dp[i] 初始值必须是 1（自己单独成队），漏初始化会导致答案偏小。进阶 O(n log n) 用“贪心 + 二分维护上升序列末尾最小值”，笔试常考两种复杂度对比。

三、背包问题（最经典模型）

3.1 01 背包：每件最多选 1 次

状态：dp[j] = 容量为 j 时能装的最大价值。候选："放"或"不放"。

C++ 实例

#include <iostream>
using namespace std;
const int M = 10005;
int dp[M];                    // dp[j]: 容量为 j 的背包能装的最大价值
int main() {
    int n, C;                 // n 件物品，背包容量 C
    cin >> n >> C;
    for (int i = 0; i < n; i++) {
        int w, v;             // 当前物品：重量、价值
        cin >> w >> v;
        // 01 背包：每件物品最多选一次，容量必须逆序枚举
        for (int j = C; j >= w; j--) {   // 逆序防止同一物品被重复选取
            dp[j] = max(dp[j], dp[j - w] + v);  // 不选 vs 选
        }
    }
    cout << dp[C] << endl;    // 容量 C 时的最优价值
    return 0;
}

为什么逆序：正序会让同一物品被反复选（变成完全背包）。这是面试/笔试最爱问的一点。

3.2 完全背包：每件可选无限次

C++ 实例

// 完全背包：物品无限取用，容量正序枚举即可
for (int i = 0; i < n; i++) {
    int w, v; cin >> w >> v;
    for (int j = w; j <= C; j++) {      // 正序遍历即可无限选
        dp[j] = max(dp[j], dp[j - w] + v);
    }
}

01 背包（逆序） ↔ 完全背包（正序），只差一个循环顺序。

3.3 多重背包：有数量限制

可"二进制拆分"转 01 背包（进阶）或直接三层循环（数据小时）。

形象理解背包像行李箱装箱：每件物品“装 or 不装”都试一遍，记下每个容量下最好的装法。01 背包每件只能装一次，完全背包像矿泉水无限供应可以反复装。

易错点01 背包必须容量倒序（for j = C; j >= w; j--），完全背包正序（for j = w; j <= C; j++）。循环方向搞反是背包题最高频错误——倒序防止同一件被反复取，正序允许无限取。

四、坐标 DP：数字三角形

C++ 实例

// 数字三角形：从顶部走到底部，路径上数字和最大
// 状态转移：dp[i][j] = max(左上, 正上) + 当前值
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 105;
int a[N][N], dp[N][N];
int main() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++) cin >> a[i][j];
    for (int i = 1; i <= n; i++)               // 逐行递推
        for (int j = 1; j <= i; j++)
            dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + a[i][j];
    int ans = 0;
    for (int j = 1; j <= n; j++) ans = max(ans, dp[n][j]);   // 底部取最大
    cout << ans << endl;
    return 0;
}

二维网格 DP（走格子最小代价 / 路径数）同理，是坐标 DP 的基座。

形象理解数字三角形像从山顶下山选路拿最多金币：每走一步只能往左下方或右下方，dp[i][j] 记“走到第 i 行第 j 个数时最多拿到多少”。从上往下推：dp[i][j] = max(左上, 右上) + a[i][j]。

易错点坐标 DP 注意边界列：三角形最左/最右只有一条来路，用 dp[i-1][j-1] 和 dp[i-1][j] 时越界的格子当作 0 处理即可，别让下标越界。

五、区间 DP：石子合并 / 括号配对

状态 dp[i][j]：区间 [i, j] 的最优解；转移枚举"最后一步"的分割点 k。

C++ 实例

// 合并石子（线性版）：合并相邻两堆，代价为两堆之和，求最小总代价
#include <iostream>
using namespace std;
const int N = 305;
const int INF = 1e9;
int stone[N], pre[N], dp[N][N];   // pre 前缀和：O(1) 求区间石子总数
int main() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) { cin >> stone[i]; pre[i] = pre[i - 1] + stone[i]; }
    for (int len = 2; len <= n; len++) {           // 枚举区间长度（区间 DP 外层）
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;                   // 区间右端点
            dp[i][j] = INF;
            for (int k = i; k < j; k++) {          // 枚举分割点
                dp[i][j] = min(dp[i][j],
                    dp[i][k] + dp[k + 1][j] + (pre[j] - pre[i - 1]));  // 左+右+本次合并代价
            }
        }
    }
    cout << dp[1][n] << endl;    // 全部合并成一堆的最小代价
    return 0;
}

区间 DP 模板结构：先枚举长度 len，再枚举起点，三重循环。

形象理解区间 DP 像规划合并快递包裹的顺序：dp[i][j] 表示把区间 [i,j] 的包裹合并成一堆的最小代价，枚举“最后一次合并在哪一刀切”（分割点 k），左右两堆先各自合并再加总。

易错点区间 DP 循环顺序必须先枚举长度 len，再枚举起点 i：因为长区间的答案依赖更短区间，外层长度才能保证被依赖的 dp[i][k] 已算好。写成“先起点后长度”会用到未计算状态，答案全错。

六、树形 DP 与 DAG DP（进阶预告）

树形 DP：在树上做 DP，如"最大独立集（选/不选）、树上背包、树的直径"。用 DFS 后序遍历合并子树结果。
DAG 上 DP/最长路：拓扑序 DP 递推（结合 11 章）。

C++ 实例

// 树形 DP 小样：选父节点则不能选子节点（最大权独立集）
// 递归后序更新：
// dp[u][选] = w[u] + sum(dp[子][不选])
// dp[u][不选] = sum(max(dp[子][选], dp[子][不选]))

七、DP 优化方向（NOIP 进阶）

滚动数组：只保留两行/一维，降空间。
单调队列优化 / 斜率优化 / 四边形不等式（提高组）。
状态压缩 DP（17 章）：把集合状态压成二进制位。
记忆化搜索 ↔ DP：写递归带 memo 等价于递推 DP。

八、易错点 / 常见坑点

⚠️ 状态定义不清导致转移写错。先想清楚"状态到底是什么、从哪里来"。
⚠️ 01 背包与完全背包循环方向搞反。
⚠️ 忘记初始化边界（如求最小值时初始化为 INF，求最大值时初始化为 0 或 -INF）。
⚠️ 区间 DP 循环顺序错误（必须外层长度、内层起点），否则用到未计算状态。
⚠️ DP 数组维度不够 / 下标越界。
⚠️ 把"能用贪心的题"硬套 DP 或反之，先分析再动手。
⚠️ 结果溢出用 long long（如方案数、大价值求和）。

九、考级要求 vs 竞赛进阶

考级要求（GESP 6 级）：线性 DP（LIS、最大子段和）、数字三角形、01 背包、简单坐标 DP；重点在"理解递推与状态转移"。
竞赛进阶（CSP-J/NOIP）：01/完全/多重背包变式（多重背包二进制优化、分组背包、依赖背包）、区间 DP、树形 DP、DAG DP、状态压缩 DP；DP 是 CSP-J 第 4 题和 NOIP 的核心考点。

十、课内练习建议

先做数字三角形 → 最大子段和 → LIS 三连练，体会"状态定义"。
01 背包 + 完全背包各写一遍，对比循环方向。
用滚动数组把 01 背包从二维降到一维。
石子合并（区间 DP）手工推 4 堆样例。
做做"最长公共子序列（LCS）"——另一种线性 DP 经典。