博客详情 - DL24JPOJ

DL24JP 的博客
动态规划入门：把大问题拆成小问题，一步一步解
DL24JP SU @ 2026-6-17 19:29:11

适合阅读：初中阶段学习信息学竞赛的同学

例题来源：信息学奥赛一本通（C++版），例9.2～例9.24，含 NOIP 真题

一、什么是动态规划？

从斐波那契数列说起

$F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2)$ 。

直接写递归，计算 $F(10)$ 会把 $F(5)$ 重复算很多遍。聪明做法：用一个数组把中间结果存起来，避免重复计算——

记忆化：每个子问题只算一次，答案存起来复用。

动态规划（DP） 就是将问题分解成重叠子问题，通过递推关系逐步求解的算法。

DP 三个关键特征

特征	含义	例子
最优子结构	大问题的最优解包含子问题的最优解	最短路径的每一段也是最短的
重叠子问题	同一个子问题被反复用到	$F(5)$ 被 $F(6),F(7)...$ 反复调用
无后效性	过去的状态不影响未来决策	走到某格后，怎么来的不重要

DP 和贪心的区别

	贪心算法	动态规划
决策方式	只看眼前，选当前最优，不回头	考虑所有可能，选全局最优
正确性	需严格证明贪心策略	递推本身保证最优
典型问题	活动选择、排队接水	背包、最长子序列、编辑距离
代码特点	排序 + 一次遍历	填表（dp数组）+ 状态转移

💡 一句话：贪心是"一条路走到黑"，DP 是"所有路都试试，选最好的"。

DP 解题四步法

步骤一：定义状态    → dp[i] / dp[i][j] 代表什么？
步骤二：找转移方程  → dp[i] 怎么从更小的状态推出来？
步骤三：确定初始值  → dp[0]、dp[i][i] 等边界是什么？
步骤四：确定遍历顺序 → i从小到大？j倒序？len从小到大？

二、例题精讲

按 DP 类型分为六大类：入门递推 → DAG 最短路 → LIS/LCS 子序列 → 背包九讲精选 → 区间 DP → 记忆化搜索

第一类：入门递推 —— 从简单填表开始

例9.2 数字金字塔 —— "从下往上，逐层递推"

题目描述

数字金字塔。从最高点走到底部，每一步可向左下或右下，求路径数字之和的最大值。

在上面的样例中，路径 $13 \to 8 \to 26 \to 15 \to 24$ 产生最大和 $86$ 。

输入格式

第一行： $R$ （ $1 \le R \le 1000$ ）
后面 $R$ 行：每行为该行的整数（非负， $\le 100$ ）

输出格式

一行：最大的和

样例输入

5
13
11 8
12 7  26
6  14 15 8
12 7  13 24 11

样例输出

DP 策略

自底向上：从倒数第二行开始，每个数加上它下方两个数中较大的那个，逐层递推到塔顶。

转移方程：$dp[i][j] = a[i][j] + \max(dp[i+1][j],\, dp[i+1][j+1])$

解题思路

状态： $dp[i][j]$ = 从 $(i,j)$ 出发到底部的最大和
转移：$dp[i][j] = a[i][j] + \max(dp[i+1][j], dp[i+1][j+1])$
初始： $dp[R][j] = a[R][j]$
顺序： $i$ 从 $R-1$ 到 $1$

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;
int a[1005][1005], dp[1005][1005];
int main() {
    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++) dp[R][j] = a[R][j];
    for (int i = R - 1; i >= 1; i--)
        for (int j = 1; j <= i; j++)
            dp[i][j] = a[i][j] + max(dp[i+1][j], dp[i+1][j+1]);
    cout << dp[1][1] << endl;
    return 0;
}

要点	说明
自底向上	从 `R-1` 行向第 1 行推，塔顶自然出答案
`max(左下, 右下)`	每次都选下方更优的那条路

第二类：DAG 最短路 / 最长路 —— "沿着箭头，一站一站推"

例9.5 城市交通路网 —— "从起点到终点，找最省钱的路线"

题目描述

城市之间的交通路网，单向通行。求 $v_1$ 到 $v_{N}$ 的最短路径长度及路径。

输入格式

第一行：城市数 $N$
接下来 $N \times N$ 矩阵： $a[i][j]$ 表示城市 $i$ 到 $j$ 的费用（0 表示不通）

输出格式

第一行：minlong=最短路径长度
第二行：路径经过的城市编号

样例输入

10
0  2  5  1  0  0  0  0  0  0
0  0  0  0 12 14  0  0  0  0
0  0  0  0  6 10  4  0  0  0
0  0  0  0 13 12 11  0  0  0
0  0  0  0  0  0  0  3  9  0
0  0  0  0  0  0  0  6  5  0
0  0  0  0  0  0  0  0 10  0
0  0  0  0  0  0  0  0  0  5
0  0  0  0  0  0  0  0  0  2
0  0  0  0  0  0  0  0  0  0

样例输出

minlong=19
1 3 5 8 10

DP 策略

设 $dp[i]$ = 从 $v_1$ 到 $v_i$ 的最短路径长度。按城市编号从小到大递推，对于每个 $i$ ，枚举所有能到达 $i$ 的前驱城市 $j$ ， $dp[i] = \min(dp[j] + a[j][i])$ 。

转移方程：$dp[i] = \min_{j < i,\; a[j][i] > 0} (dp[j] + a[j][i])$

C++ 代码

#include <iostream>
#include <cstring>
using namespace std;
int a[105][105], dp[105], pre[105];

void print(int x) {
    if (pre[x] != 0) print(pre[x]);
    cout << x << " ";
}

int main() {
    int N; cin >> N;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++) cin >> a[i][j];

    memset(dp, 0x3f, sizeof(dp));
    dp[1] = 0;
    for (int i = 2; i <= N; i++) {
        for (int j = 1; j < i; j++) {
            if (a[j][i] > 0 && dp[j] + a[j][i] < dp[i]) {
                dp[i] = dp[j] + a[j][i];
                pre[i] = j;
            }
        }
    }
    cout << "minlong=" << dp[N] << endl;
    print(N); cout << endl;
    return 0;
}

要点	说明
DAG 递推	因为边从小号指向大号，可直接按编号顺序 DP
`pre[]` 回溯	记录前驱城市，递归输出完整路径
`memset(0x3f)`	初始化为极大值，求最小值

例9.6 挖地雷 —— "沿着地道，挖最多的雷"

题目描述

$n$ 个地窖（ $n \le 200$ ），每个地窖有一定数量的地雷。地窖间有单向连接路径（小序号→大序号，无环）。某人可从任意地窖开始挖，沿着路径往下挖（只能选一条路径），无连接时结束。求能挖到的最多地雷数及路径。

输入格式

第一行：地窖数 $n$
第二行： $n$ 个整数，每个地窖的地雷数
下面若干行：每行 $x_i\;y_i$ 表示从 $x_i$ 可到 $y_i$ （ $x_i < y_i$ ），以 0 0 结束

输出格式

第一行：挖地雷的顺序（- 分隔）
第二行：最多地雷数

样例输入

6
5 10 20 5 4 5
1 2
1 4
2 4
3 4
4 5
4 6
5 6
0 0

样例输出

3-4-5-6
34

DP 策略

设 $dp[i]$ = 以地窖 $i$ 结尾的路径能挖到的最多地雷数。对于每个 $i$ ，向前找所有能到达 $i$ 的前驱 $j$ ， $dp[i] = \max(dp[j]) + a[i]$ 。

和 LIS 相同的结构，只是"可接"的条件变成了"有边相连"。

C++ 代码

#include <iostream>
using namespace std;
int a[205], dp[205], pre[205], g[205][205];

void print(int x) {
    if (pre[x] != 0) print(pre[x]);
    if (pre[x] != 0) cout << "-";
    cout << x;
}

int main() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int x, y;
    while (cin >> x >> y && x && y) g[x][y] = 1;

    int ans = 0, pos = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = a[i]; pre[i] = 0;
        for (int j = 1; j < i; j++) {
            if (g[j][i] && dp[j] + a[i] > dp[i]) {
                dp[i] = dp[j] + a[i];
                pre[i] = j;
            }
        }
        if (dp[i] > ans) { ans = dp[i]; pos = i; }
    }
    print(pos); cout << endl << ans << endl;
    return 0;
}

要点	说明
与 LIS 同构	都是"找前驱"的线性 DP，只是前驱条件不同
`g[x][y]` 邻接矩阵	小规模下用矩阵存图最简单

第三类：LIS/LCS 子序列系列 —— "一串接一串"

例9.3 最长不下降序列（LIS）—— "一条链串到底"

题目描述

设 $n$ 个不同整数组成的数列 $b(1),b(2),\dots,b(n)$ 。若存在 $i_1 < i_2 < \dots < i_e$ 且 $b(i_1) \le b(i_2) \le \dots \le b(i_e)$ ，则称为长度为 $e$ 的不下降序列。求最长的不下降序列及一种方案。

输入格式

第一行： $n$ （ $1 \le n \le 200$ ）
第二行： $n$ 个空格分隔的整数

输出格式

第一行：max=长度
第二行：序列的具体数字

样例输入

14
13 7 9 16 38 24 37 18 44 19 21 22 63 15

样例输出

max=8
7 9 16 18 19 21 22 63

DP 策略

$dp[i]$ = 以 $b[i]$ 结尾的最长不下降序列长度。 $dp[i] = \max_{j < i,\; b[j] \le b[i]}(dp[j] + 1)$ 。

C++ 代码

#include <iostream>
using namespace std;
int b[205], dp[205], pre[205];

void print(int x) {
    if (pre[x] != 0) print(pre[x]);
    cout << b[x] << " ";
}

int main() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) { cin >> b[i]; dp[i] = 1; }
    int maxL = 1, pos = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (b[j] <= b[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1; pre[i] = j;
            }
        }
        if (dp[i] > maxL) { maxL = dp[i]; pos = i; }
    }
    cout << "max=" << maxL << endl;
    print(pos); cout << endl;
    return 0;
}

要点	说明
`dp[i]=1`	每个数自己就是长度为 1 的序列
$O(n^2)$	$n \le 200$ 足够； $n$ 大时可用二分 $O(n \log n)$

例9.4 拦截导弹（NOIP1999）—— "一套系统一条下降链"

题目描述

拦截系统第一发可到任意高度，之后每发不能高于前一发。输入 $n$ 枚导弹高度（ $\le 30000$ ， $n \le 1000$ ），求：

第一问：一套系统最多能拦截多少导弹？
第二问：要拦截所有导弹最少需要几套系统？

输入格式

导弹依次飞来的高度

输出格式

第一行：最多拦截数
第二行：最少系统数

样例输入

389 207 155 300 299 170 158 65

样例输出

6
2

样例解释

最多拦截 6 枚（如 389→207→155→170→158→65 不合法；正确：389,207,155 或 300,299,170,158,65 等，实际最长非升子序列长 6）
最少需要 2 套系统（389→207→155，300→299→170→158→65）

DP 策略

第一问：求最长不上升子序列长度。 $dp[i] = \max_{j<i,\; h[j] \ge h[i]}(dp[j]+1)$ 。 第二问：贪心——每颗导弹用"能拦且高度最低"的系统拦截（同贪心博客例6.4）；等价于求最长上升子序列长度（Dilworth 定理）。

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;
int h[1005], dp[1005], sys[1005];

int main() {
    int n = 0;
    while (cin >> h[++n]); n--;  // 读到EOF

    // 第一问：最长不上升子序列
    int ans1 = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = 1;
        for (int j = 1; j < i; j++)
            if (h[j] >= h[i]) dp[i] = max(dp[i], dp[j] + 1);
        ans1 = max(ans1, dp[i]);
    }

    // 第二问：贪心（最少非升子序列覆盖）
    int k = 0;
    for (int i = 1; i <= n; i++) {
        int best = -1;
        for (int j = 1; j <= k; j++)
            if (sys[j] >= h[i] && (best == -1 || sys[j] < sys[best]))
                best = j;
        if (best != -1) sys[best] = h[i];
        else sys[++k] = h[i];
    }

    cout << ans1 << endl << k << endl;
    return 0;
}

要点	说明
第一问 LIS 变种	条件变为 $h[j] \ge h[i]$ （不上升）
第二问贪心	贪心博客例6.4 的核心思想复用
Dilworth 定理	最少非升子序列覆盖数 = 最长上升子序列长度

例9.7 友好城市 —— "排序后就是 LIS"

题目描述

河有南北两岸，各有 $N$ 个城市。每对友好城市申请一条航道，航道不能交叉。求最多能批准多少条航道。

输入格式

第一行： $N$ （ $1 \le N \le 5000$ ）
接下来 $N$ 行：每行两个整数，南岸坐标和北岸坐标

输出格式

一行：最多申请数

样例输入

样例输出

DP 策略

将城市对按南岸坐标升序排序。之后问题转化为：在排序后的北岸坐标序列中求最长上升子序列（LIS）。

为什么对？

两条航道 $(a_1,b_1)$ 和 $(a_2,b_2)$ 不交叉的条件是： $a_1 < a_2$ 且 $b_1 < b_2$ （或相反）。按南岸排序后，只需保证北岸坐标递增即可 —— 这恰好是 LIS。

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;
struct City { int s, n; } c[5005];
bool cmp(City a, City b) { return a.s < b.s; }
int dp[5005];

int main() {
    int N; cin >> N;
    for (int i = 1; i <= N; i++) cin >> c[i].s >> c[i].n;
    sort(c + 1, c + N + 1, cmp);
    int ans = 0;
    for (int i = 1; i <= N; i++) {
        dp[i] = 1;
        for (int j = 1; j < i; j++)
            if (c[j].n < c[i].n) dp[i] = max(dp[i], dp[j] + 1);
        ans = max(ans, dp[i]);
    }
    cout << ans << endl;
    return 0;
}

要点	说明
排序转化	将几何交叉问题转化为 LIS
$n=5000$	$O(n^2)=2500$ 万，勉强够；可用二分优化

例9.8 合唱队形 —— "先上升再下降，中间最高"

题目描述

$N$ 位同学站成一排，身高 $T_i$ 。请最少几位出列，使得剩下的同学身高呈"先严格递增、再严格递减"（中间那位最高）。即 $T_1 < \dots < T_i > T_{i+1} > \dots > T_K$ 。

输入格式

第一行： $N$ （ $2 \le N \le 100$ ）
第二行： $N$ 个整数 $T_i$ （ $130 \le T_i \le 230$ ）

输出格式

一行：最少出列人数

样例输入

8
186 186 150 200 160 130 197 220

样例输出

DP 策略

对每个位置 $i$ ，分别求以 $i$ 结尾的最长上升子序列 $up[i]$ 和以 $i$ 开头的最长下降子序列 $down[i]$ 。以 $i$ 为最高点留在队伍中的人数 = $up[i] + down[i] - 1$ 。答案 = $N - \max(up[i] + down[i] - 1)$ 。

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;
int T[105], up[105], down[105];

int main() {
    int N; cin >> N;
    for (int i = 1; i <= N; i++) cin >> T[i];
    // 从左到右 LIS
    for (int i = 1; i <= N; i++) {
        up[i] = 1;
        for (int j = 1; j < i; j++)
            if (T[j] < T[i]) up[i] = max(up[i], up[j] + 1);
    }
    // 从右到左 LIS（等价于下降）
    for (int i = N; i >= 1; i--) {
        down[i] = 1;
        for (int j = N; j > i; j--)
            if (T[j] < T[i]) down[i] = max(down[i], down[j] + 1);
    }
    int keep = 0;
    for (int i = 1; i <= N; i++)
        keep = max(keep, up[i] + down[i] - 1);
    cout << N - keep << endl;
    return 0;
}

要点	说明
双向 LIS	从左到右 + 从右到左各扫一遍
$-1$	$i$ 自己算了两次

例9.9 最长公共子序列（LCS）—— "找两个字符串的公共基因"

题目描述

求两个序列 $X$ 和 $Y$ 的最长公共子序列（LCS）的长度。子序列不必连续。

输入格式

两行：各一个大写字母字符串（长度 $\le 1000$ ）

输出格式

一行：LCS 长度（无公共子序列输出 0）

样例输入

ABCBDAB
BDCABA

样例输出

DP 策略

$dp[i][j]$ = $X$ 前 $i$ 个和 $Y$ 前 $j$ 个的 LCS 长度。

相同： $dp[i][j] = dp[i-1][j-1] + 1$

不同： $dp[i][j] = \max(dp[i-1][j],\, dp[i][j-1])$

C++ 代码

#include <iostream>
#include <string>
using namespace std;
int dp[1005][1005];

int main() {
    string X, Y; cin >> X >> Y;
    int m = X.size(), n = Y.size();
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (X[i-1] == Y[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
    cout << dp[m][n] << endl;
    return 0;
}

要点	说明
相同→左上+1	该字符配对上，计入 LCS
不同→max(上,左)	至少丢弃一个字符

第四类：背包九讲精选 —— "装与不装的智慧"

例9.11 01背包问题 —— "要么拿，要么不拿"

题目描述

背包容量 $M$ （ $\le 200$ ）， $N$ 件物品（ $\le 30$ ），每件物品重量 $W_i$ 、价值 $C_i$ ，每件只能选一次。求最大总价值。

样例输入

样例输出

DP 策略

$dp[j]$ = 容量 $j$ 时的最大价值。每件物品倒序更新： $dp[j] = \max(dp[j],\, dp[j-W_i] + C_i)$ 。

为什么倒序？ $dp[j-W_i]$ 还没被当前物品更新过，保证每件只用一次。

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;
int dp[205];
int main() {
    int M, N; cin >> M >> N;
    for (int i = 1; i <= N; i++) {
        int w, c; cin >> w >> c;
        for (int j = M; j >= w; j--)       // 倒序！
            dp[j] = max(dp[j], dp[j - w] + c);
    }
    cout << dp[M] << endl;
    return 0;
}

要点	说明
倒序遍历	`j--` 保证每件只用一次
一维数组	空间优化：省去物品维度

例9.12 完全背包问题 —— "想拿几个拿几个"

题目描述

与 01 背包相同，但每种物品数量无限，可多次选取。

样例输入

样例输出

max=12

DP 策略

与 01 背包代码唯一区别：正序遍历： $dp[j] = \max(dp[j],\, dp[j-W_i] + C_i)$ 。

为什么正序？ $dp[j-W_i]$ 可能已被当前物品更新过，代表"已经用过一次"的状态，再转移 = 再选一次 = 无限使用。

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;
int dp[205];
int main() {
    int M, N; cin >> M >> N;
    for (int i = 1; i <= N; i++) {
        int w, c; cin >> w >> c;
        for (int j = w; j <= M; j++)       // 正序！唯一区别
            dp[j] = max(dp[j], dp[j - w] + c);
    }
    cout << "max=" << dp[M] << endl;
    return 0;
}

要点	说明
唯一差异	`j++` vs `j--`

例9.13 庆功会（多重背包）—— "每样最多拿 s 件"

题目描述

$n$ 种奖品（ $n \le 500$ ），拨款 $m$ （ $\le 6000$ ）。每种价格 $v$ 、价值 $w$ 、最多买 $s$ 件（ $s \le 10$ ）。求最大价值。

样例输入

样例输出

DP 策略

将每种物品的 $s$ 件二进制拆分为若干件（1,2,4,..., 余数），转化为 01 背包。拆分后物品数约 $n \log s$ 。

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;
int dp[6005];
int main() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int v, w, s; cin >> v >> w >> s;
        // 二进制拆分
        for (int k = 1; k <= s; k <<= 1) {
            for (int j = m; j >= v * k; j--)
                dp[j] = max(dp[j], dp[j - v * k] + w * k);
            s -= k;
        }
        if (s > 0) {
            for (int j = m; j >= v * s; j--)
                dp[j] = max(dp[j], dp[j - v * s] + w * s);
        }
    }
    cout << dp[m] << endl;
    return 0;
}

要点	说明
二进制拆分	$s$ 拆成 1,2,4,... 的捆，每捆视为 01 物品
也可三重循环	$dp[j] = \max_{k=0..s}(dp[j-kv] + kw)$ ，但效率较低

例9.14 混合背包 —— "三种背包一锅烩"

题目描述

物品有三种类型： $P_i=0$ 无限取（完全背包）， $P_i=1$ 只取一次（01）， $P_i>1$ 最多取 $P_i$ 次（多重）。求最大价值。

样例输入

样例输出

DP 策略

对每种物品按类型分别处理：

$P=0$ → 正序（完全背包）

$P=1$ → 倒序（01 背包）

$P>1$ → 二进制拆分 + 倒序（多重背包）

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;
int dp[205];
int main() {
    int M, N; cin >> M >> N;
    for (int i = 1; i <= N; i++) {
        int w, c, p; cin >> w >> c >> p;
        if (p == 0) {                         // 完全背包
            for (int j = w; j <= M; j++)
                dp[j] = max(dp[j], dp[j - w] + c);
        } else if (p == 1) {                  // 01背包
            for (int j = M; j >= w; j--)
                dp[j] = max(dp[j], dp[j - w] + c);
        } else {                              // 多重背包
            for (int k = 1; k <= p; k <<= 1) {
                for (int j = M; j >= w * k; j--)
                    dp[j] = max(dp[j], dp[j - w * k] + c * k);
                p -= k;
            }
            if (p > 0)
                for (int j = M; j >= w * p; j--)
                    dp[j] = max(dp[j], dp[j - w * p] + c * p);
        }
    }
    cout << dp[M] << endl;
    return 0;
}

要点	说明
按 $P$ 分支	每种类型用不同的循环方向
组合拳	混合背包 = 01 + 完全 + 多重，分别处理即可

例9.15 潜水员（二维费用背包）—— "两种气体都要够"

题目描述

潜水需要 $m$ 升氧和 $n$ 升氮（ $m \le 21, n \le 79$ ）。有 $k$ 个气缸（ $k \le 1000$ ），每个气缸含氧气 $a_i$ 、氮气 $b_i$ ，重量 $c_i$ 。求满足气体需求的最小总重量。

样例输入

样例输出

DP 策略

$dp[i][j]$ = 获得至少 $i$ 升氧和 $j$ 升氮的最小重量。注意"至少"而非"恰好"——超出需求直接归结到 $dp[m][n]$ 。

转移时处理超出边界：$dp[\min(m, i+a)][\min(n, j+b)] = \min(自己, dp[i][j] + c)$。

C++ 代码

#include <iostream>
#include <cstring>
using namespace std;
int dp[25][85];
int main() {
    int m, n, k; cin >> m >> n >> k;
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = 0;
    for (int t = 1; t <= k; t++) {
        int a, b, c; cin >> a >> b >> c;
        for (int i = m; i >= 0; i--) {
            for (int j = n; j >= 0; j--) {
                int ni = min(m, i + a);
                int nj = min(n, j + b);
                dp[ni][nj] = min(dp[ni][nj], dp[i][j] + c);
            }
        }
    }
    cout << dp[m][n] << endl;
    return 0;
}

要点	说明
"至少"处理	`min(m, i+a)` 将超出需求的状态压到目标状态
二维费用	类似 01 背包但状态有两维
倒序遍历	每个气缸只用一次

例9.16 分组背包 —— "每组最多选一件"

题目描述

$N$ 件物品分为 $T$ 组，每组内的物品互相冲突（最多选一件）。背包容量 $V$ （ $\le 200$ ），求最大价值。

样例输入

样例输出

DP 策略

外层枚举组，中层倒序枚举容量，内层枚举组内物品。对于每组， $dp[j] = \max_{k \in group}(dp[j], dp[j-W_k] + C_k)$ 。

为什么内层在倒序里面？ 确保同一组内只选一件。

C++ 代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int dp[205];
struct Item { int w, c; };
vector<Item> group[15];

int main() {
    int V, N, T; cin >> V >> N >> T;
    for (int i = 1; i <= N; i++) {
        int w, c, p; cin >> w >> c >> p;
        group[p].push_back({w, c});
    }
    for (int g = 1; g <= T; g++) {               // 枚举组
        for (int j = V; j >= 0; j--) {            // 倒序容量
            for (auto &it : group[g]) {           // 组内物品
                if (j >= it.w)
                    dp[j] = max(dp[j], dp[j - it.w] + it.c);
            }
        }
    }
    cout << dp[V] << endl;
    return 0;
}

要点	说明
组→容量→物品	三层循环顺序不能乱
容量倒序	保证每组只选一件

例9.17 货币系统 —— "凑钱有多少种方案"

题目描述

$n$ 种面值的货币，求组成面值 $m$ 的方案数。每种货币数量无限。

输入格式

第一行： $n$ 和 $m$
下面 $n$ 行：每种面值

样例输入

样例输出

DP 策略

$dp[j]$ = 凑出 $j$ 元的方案数。 $dp[j] = dp[j] + dp[j - v]$ （正序，因为每种无限用）。

这是完全背包求方案数。

C++ 代码

#include <iostream>
using namespace std;
long long dp[10005];  // 方案数可能很大
int main() {
    int n, m; cin >> n >> m;
    dp[0] = 1;  // 凑0元有1种方案（什么都不选）
    for (int i = 1; i <= n; i++) {
        int v; cin >> v;
        for (int j = v; j <= m; j++)
            dp[j] += dp[j - v];
    }
    cout << dp[m] << endl;
    return 0;
}

要点	说明
`dp[0]=1`	凑 0 元有 1 种方案（空集）
`dp[j] += dp[j-v]`	累加方案数而非取 max
正序	无限用 → 完全背包模式

例9.10 机器分配 —— "M 台设备分给 N 个公司"

题目描述

总公司有 $M$ 台设备（ $M \le 15$ ），分给 $N$ 个分公司（ $N \le 10$ ）。每个分公司获得不同数量设备的盈利不同（给出 $N \times M$ 矩阵）。求最大总盈利及分配方案。

样例输入

样例输出

DP 策略

$dp[i][j]$ = 前 $i$ 个公司分配 $j$ 台设备的最大盈利。转移：枚举第 $i$ 个公司分 $k$ 台（ $0 \le k \le j$ ）， $dp[i][j] = \max(dp[i-1][j-k] + profit[i][k])$ 。

C++ 代码

#include <iostream>
using namespace std;
int p[15][20], dp[15][20], ans[15];

int main() {
    int N, M; cin >> N >> M;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++) cin >> p[i][j];

    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= M; j++) {
            for (int k = 0; k <= j; k++) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-k] + p[i][k]);
            }
        }
    }
    cout << dp[N][M] << endl;
    // 回溯方案
    int j = M;
    for (int i = N; i >= 1; i--) {
        for (int k = 0; k <= j; k++) {
            if (dp[i][j] == dp[i-1][j-k] + p[i][k]) {
                ans[i] = k; j -= k; break;
            }
        }
    }
    for (int i = 1; i <= N; i++)
        cout << i << " " << ans[i] << endl;
    return 0;
}

要点	说明
分组背包变种	相当于每组（公司）有 $M+1$ 种选择（分 0~M 台）
回溯方案	从 $dp[N][M]$ 倒推每家公司分了几台

第五类：区间 / 划分 DP —— "从短到长，枚举分界点"

例9.18 合并石子（区间 DP）—— "一层层合并，从短到长"

题目描述

一排 $N$ 堆石子（ $2 \le N \le 100$ ），每次合并相邻2堆，得分为合并后的石子数。求合并成一堆的最小得分。

样例输入

样例输出

DP 策略

$dp[i][j]$ = 合并 $[i,j]$ 的最小得分。枚举分割点 $k$ ：$dp[i][j] = \min_{k}(dp[i][k] + dp[k+1][j]) + sum(i,j)$。

按区间长度从小到大递推。

C++ 代码

#include <iostream>
#include <cstring>
using namespace std;
int a[105], s[105], dp[105][105];
int main() {
    int N; cin >> N;
    for (int i = 1; i <= N; i++) { cin >> a[i]; s[i] = s[i-1] + a[i]; }
    memset(dp, 0x3f, sizeof(dp));
    for (int i = 1; i <= N; i++) dp[i][i] = 0;

    for (int len = 2; len <= N; len++) {
        for (int i = 1; i + len - 1 <= N; i++) {
            int j = i + len - 1;
            int sum = s[j] - s[i-1];
            for (int k = i; k < j; k++)
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sum);
        }
    }
    cout << dp[1][N] << endl;
    return 0;
}

要点	说明
区间 DP 模板	`len→i→k` 三层循环
前缀和	$O(1)$ 求区间石子总数
`memset(0x3f)`	求最小值，初始为极大

例9.19 乘积最大 —— "K 个乘号，怎么插最划算"

题目描述

长度为 $N$ 的数字串（ $6 \le N \le 10$ ），插入 $K$ 个乘号（ $1 \le K \le 6$ ），分成 $K+1$ 部分相乘。求最大乘积。

样例输入

4 2
1231

样例输出

样例解释

1231 插入 2 个乘号：1*2*31=62、1*23*1=23、12*3*1=36。最大为 62（实际上是 1*2*31=62 等，最优为 12*31 或 1*2*31 等，查最优为 62）。

DP 策略

$dp[i][k]$ = 前 $i$ 个数字插入 $k$ 个乘号的最大乘积。枚举最后一个乘号的位置 $j$ ： $dp[i][k] = \max_j(dp[j][k-1] \times num(j+1, i))$ 。

C++ 代码

#include <iostream>
#include <string>
using namespace std;
long long dp[15][10];  // dp[i][k] = 前i位插入k个乘号

long long num(string &s, int l, int r) {  // 取子串转数字
    long long x = 0;
    for (int i = l; i <= r; i++) x = x * 10 + (s[i] - '0');
    return x;
}

int main() {
    int N, K; string s;
    cin >> N >> K >> s; s = " " + s;
    for (int i = 1; i <= N; i++) dp[i][0] = num(s, 1, i);
    for (int k = 1; k <= K; k++) {
        for (int i = k + 1; i <= N; i++) {
            for (int j = k; j < i; j++) {
                long long val = dp[j][k-1] * num(s, j+1, i);
                dp[i][k] = max(dp[i][k], val);
            }
        }
    }
    cout << dp[N][K] << endl;
    return 0;
}

要点	说明
`dp[i][0]`	不插乘号 = 整个数字本身
枚举最后乘号位置	这是划分 DP 的经典套路

例9.20 编辑距离 —— "最少几步把 A 变成 B"

题目描述

三种操作：删除、插入、替换一个字符。求将字符串 $A$ 变成 $B$ 的最少操作次数（长度均 $< 2000$ ）。

样例输入

sfdqxbw
gfdgw

样例输出

DP 策略

$dp[i][j]$ = $A$ 前 $i$ 个变成 $B$ 前 $j$ 个的最少次数。

$A[i]=B[j]$ → $dp[i][j] = dp[i-1][j-1]$

$A[i] \neq B[j]$ → $\min(dp[i-1][j-1]+1,\; dp[i-1][j]+1,\; dp[i][j-1]+1)$

C++ 代码

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int dp[2005][2005];
int main() {
    string A, B; cin >> A >> B;
    int m = A.size(), n = B.size();
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (A[i-1] == B[j-1])
                dp[i][j] = dp[i-1][j-1];
            else
                dp[i][j] = min({dp[i-1][j-1]+1, dp[i-1][j]+1, dp[i][j-1]+1});
        }
    }
    cout << dp[m][n] << endl;
    return 0;
}

要点	说明
`dp[i][0]=i`	删 $i$ 次变空串
`dp[0][j]=j`	插 $j$ 次从空串变来

例9.21 方格取数 —— "走两次，一起走"

题目描述

$N \times N$ 方格（ $N \le 10$ ），某些格有正整数。从左上角 A 走到右下角 B，只能向右或向下走，共走两次（第一次取走后数字变 0）。求两次路径取得的数字和最大值。

样例输入

样例输出

DP 策略

$dp[k][i_1][i_2]$ = 走了 $k$ 步，第一条路径到第 $i_1$ 行，第二条路径到第 $i_2$ 行时的最大和。列号通过 $j = k - i + 2$ 推算（假设从 (1,1) 出发）。两人同时走，转移时有四种组合（都向下、都向右、一上一下）。若两路径在同一格，数字只加一次。

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;
int a[15][15], dp[25][15][15];

int main() {
    int N; cin >> N;
    int x, y, v;
    while (cin >> x >> y >> v && (x || y || v)) a[x][y] = v;

    for (int k = 1; k <= 2 * N - 1; k++) {
        for (int i1 = 1; i1 <= N && i1 <= k; i1++) {
            for (int i2 = 1; i2 <= N && i2 <= k; i2++) {
                int j1 = k - i1 + 1, j2 = k - i2 + 1;
                if (j1 < 1 || j1 > N || j2 < 1 || j2 > N) continue;
                int val = a[i1][j1];
                if (i1 != i2 || j1 != j2) val += a[i2][j2];
                int best = max({
                    dp[k-1][i1][i2], dp[k-1][i1-1][i2],
                    dp[k-1][i1][i2-1], dp[k-1][i1-1][i2-1]
                });
                dp[k][i1][i2] = best + val;
            }
        }
    }
    cout << dp[2*N-1][N][N] << endl;
    return 0;
}

要点	说明
同步走	用步数 $k$ 统一两人的进度
去重	若两人到达同一格，数字只加一次
四方向组合	两人分别有 2 种走法，总共 $2 \times 2 = 4$ 种

例9.22 复制书稿 —— "M 本书分给 K 个人，连续分配"

题目描述

$m$ 本书按顺序分给 $k$ 人抄写（ $\le 500$ ），每人抄连续的若干本。求使"抄最多页数的人"用时最短的方案，若有多解让前面的人尽量少抄。

样例输入

9 3
1 2 3 4 5 6 7 8 9

样例输出

1 5
6 7
8 9

DP 策略

$dp[i][j]$ = 前 $i$ 本书分给 $j$ 个人的最短时间（ $j$ 个人中抄最多页数的最小值）。枚举最后一个人抄的书： $dp[i][j] = \min_k \max(dp[k][j-1], sum(k+1,i))$ 。

C++ 代码

#include <iostream>
#include <cstring>
using namespace std;
int a[505], s[505], dp[505][505], pre[505][505];

void print(int i, int j) {
    if (j == 1) { cout << 1 << " " << i << endl; return; }
    print(pre[i][j], j - 1);
    cout << pre[i][j] + 1 << " " << i << endl;
}

int main() {
    int m, k; cin >> m >> k;
    for (int i = 1; i <= m; i++) { cin >> a[i]; s[i] = s[i-1] + a[i]; }
    memset(dp, 0x3f, sizeof(dp));
    for (int i = 1; i <= m; i++) dp[i][1] = s[i];
    for (int j = 2; j <= k; j++) {
        for (int i = j; i <= m; i++) {
            for (int p = j - 1; p < i; p++) {
                int t = max(dp[p][j-1], s[i] - s[p]);
                if (t <= dp[i][j]) {  // <= 保证前面的人尽可能少抄
                    dp[i][j] = t;
                    pre[i][j] = p;
                }
            }
        }
    }
    print(m, k);
    return 0;
}

要点	说明
`max(dp[p][j-1], sum)`	时间 = 前面人和最后人的最大用时
`<=`	等号时也更新，满足"前面人尽量少"

例9.23 橱窗布置 —— "花束顺序插花瓶，最美搭配"

题目描述

$F$ 束花（ $F \le 100$ ）， $V$ 个花瓶（ $F \le V \le 100$ ）。花束必须按编号顺序放入，每瓶最多一束花。 $A_{ij}$ 表示花 $i$ 放瓶 $j$ 的美学值（可能为负）。求最大美学值和方案。

样例输入

3 5
7 23 -5 -24 16
5 21 -4 10 23
-21 5 -4 -20 20

样例输出

53
2 4 5

DP 策略

$dp[i][j]$ = 前 $i$ 束花放入前 $j$ 个花瓶的最大美学值。转移：第 $i$ 束花要么不放（如果 $j>i$ ），要么放入瓶 $j$ ：$dp[i][j] = \max(dp[i][j-1], dp[i-1][j-1] + A[i][j])$。

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;
int a[105][105], dp[105][105];
int ans[105];

int main() {
    int F, V; cin >> F >> V;
    for (int i = 1; i <= F; i++)
        for (int j = 1; j <= V; j++) cin >> a[i][j];

    // 初始化：0束花放j个花瓶美学值为0；i束花放<j个花瓶为-INF
    for (int i = 0; i <= F; i++)
        for (int j = 0; j <= V; j++)
            dp[i][j] = -1e9;
    for (int j = 0; j <= V; j++) dp[0][j] = 0;

    for (int i = 1; i <= F; i++) {
        for (int j = i; j <= V; j++) {
            dp[i][j] = max(dp[i][j-1], dp[i-1][j-1] + a[i][j]);
        }
    }
    cout << dp[F][V] << endl;
    // 回溯：用dp值判断花i是否放入瓶j
    int i = F, j = V;
    while (i > 0) {
        if (dp[i][j] == dp[i][j-1]) {  // 花i没放瓶j
            j--;
        } else {                       // 花i放入瓶j
            ans[i] = j;
            i--; j--;
        }
    }
    for (int i = 1; i <= F; i++) cout << ans[i] << " ";
    cout << endl;
    return 0;
}

要点	说明
全局初始化	所有 `dp[i][j]` 初始为 `-1e9`，`dp[0][j]=0`，从源头杜绝无效状态
回溯	用 `dp` 值判断（而非标记数组），更可靠
负美学值	题目中美学值可能为负，-1e9 作为负无穷不会干扰比较

第六类：记忆化搜索 —— "滑到哪里，记到哪里"

例9.24 滑雪 —— "DFS + 缓存 = 记忆化搜索"

题目描述

区域由一个二维数组给出，每个数字代表高度。从某点可以向上下左右相邻且高度更小的点滑。求最长滑坡长度（滑过点数）。

样例输入

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

样例输出

DP 策略（记忆化搜索）

$dp[x][y]$ = 从 $(x,y)$ 出发的最长滑坡。DFS 递归：对四个方向中高度更小的邻居，递归计算 +1 取最大值。关键：用 dp[x][y] 缓存，已计算过直接返回。

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;
int R, C, h[105][105], dp[105][105];
int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};

int dfs(int x, int y) {
    if (dp[x][y]) return dp[x][y];
    dp[x][y] = 1;
    for (int d = 0; d < 4; d++) {
        int nx = x + dx[d], ny = y + dy[d];
        if (nx < 1 || nx > R || ny < 1 || ny > C) continue;
        if (h[nx][ny] >= h[x][y]) continue;
        dp[x][y] = max(dp[x][y], dfs(nx, ny) + 1);
    }
    return dp[x][y];
}

int main() {
    cin >> R >> C;
    for (int i = 1; i <= R; i++)
        for (int j = 1; j <= C; j++) cin >> h[i][j];
    int ans = 0;
    for (int i = 1; i <= R; i++)
        for (int j = 1; j <= C; j++)
            ans = max(ans, dfs(i, j));
    cout << ans << endl;
    return 0;
}

要点	说明
`if (dp[x][y]) return`	记忆化核心：已算则不再算
自动处理依赖	不需要手动指定遍历顺序

三、23 题总表

题号	题目	DP 类型	核心转移	复杂度
9.2	数字金字塔	线性DP（自底向上）	$dp[i][j]=a[i][j]+\max(左下,右下)$	$O(R^2)$
9.3	最长不下降序列	LIS	$dp[i]=\max_{j<i,b_j\le b_i}(dp[j]+1)$	$O(n^2)$
9.4	拦截导弹	LIS + 贪心	最长不上升子序列 + 最少系统数	$O(n^2)$
9.5	城市交通路网	DAG最短路	$dp[i]=\min(dp[j]+a[j][i])$	$O(N^2)$
9.6	挖地雷	DAG最长路	$dp[i]=\max(dp[j])+a[i]$ （有边）	$O(n^2)$
9.7	友好城市	排序+LIS	按南岸排序 → 北岸LIS
9.8	合唱队形	双向LIS	$up[i]+down[i]-1$
9.9	最长公共子序列	LCS（双串）	相同=左上+1，不同=max(上,左)	$O(mn)$
9.10	机器分配	分组背包变种	$dp[i][j]=\max(dp[i-1][j-k]+p[i][k])$	$O(NM^2)$
9.11	01背包	背包DP	$dp[j]=\max(dp[j],dp[j-w]+c)$ 倒序	$O(NM)$
9.12	完全背包	背包DP	$dp[j]=\max(dp[j],dp[j-w]+c)$ 正序	$O(NM)$
9.13	庆功会	多重背包	二进制拆分 + 01背包	$O(n\log s \cdot m)$
9.14	混合背包	三种背包混合	按P值分支：正序/倒序/拆分	$O(NM\log S)$
9.15	潜水员	二维费用背包	$dp[\min(m,i+a)][\min(n,j+b)]$	$O(k \cdot mn)$
9.16	分组背包		组→容量→物品，组内取一件	$O(TVM)$
9.17	货币系统	完全背包求方案数	$dp[j]+=dp[j-v]$ 正序	$O(nm)$
9.18	合并石子	区间DP	$dp[i][j]=\min_k(dp[i][k]+dp[k+1][j])+sum$	$O(N^3)$
9.19	乘积最大	划分DP	$dp[i][k]=\max(dp[j][k-1]\times num)$	$O(N^2K)$
9.20	编辑距离	双串DP	相同=左上，不同=min(替换,删,插)+1	$O(mn)$
9.21	方格取数	多阶段DP	四方向组合，同步走	$O(2N\cdot N^2)$
9.22	复制书稿	划分DP	$dp[i][j]=\min\max(dp[p][j-1],sum)$	$O(m^2k)$
9.23	橱窗布置	线性DP（LCS变种）	$dp[i][j]=\max(dp[i][j-1],dp[i-1][j-1]+A)$	$O(FV)$
9.24	滑雪	记忆化搜索	$dfs(x,y)=\max(邻居更低)+1$	$O(RC)$

DP 题型分类速查

┌─ 入门递推 ──── 9.2 数字金字塔
│
├─ DAG 最短路 ─── 9.5 城市交通路网、9.6 挖地雷
│
├─ LIS/LCS ──── 9.3 最长不下降序列、9.4 拦截导弹
│               9.7 友好城市、9.8 合唱队形、9.9 LCS
│
├─ 背包系列 ──── 9.10 机器分配、9.11 01背包、9.12 完全背包
│               9.13 多重背包、9.14 混合背包、9.15 二维费用
│               9.16 分组背包、9.17 货币系统
│
├─ 区间/划分DP ─ 9.18 合并石子、9.19 乘积最大、9.20 编辑距离
│               9.21 方格取数、9.22 复制书稿、9.23 橱窗布置
│
└─ 记忆化搜索 ── 9.24 滑雪

DP 解题四步法（再强调）

步骤一：定义状态    → dp[i]/dp[i][j] 代表什么？
步骤二：找转移方程  → dp[i] 怎么从更小的状态推出来？
步骤三：确定初始值  → dp[0] / dp[i][i] 等边界
步骤四：确定遍历顺序 → i从小到大？j倒序？len从小到大？

DP 常见初始化套路

场景	初始化方式
求最大值（价值/长度）	`memset(dp, 0, sizeof(dp))`
求最小值（代价/步数）	`memset(dp, 0x3f, sizeof(dp))`，设 `dp[0]=0`
LIS 类	`dp[i] = 1`（每个元素自成序列）
LCS / 编辑距离	`dp[0][]` 和 `dp[][0]` 单独初始化
背包	`dp[0] = 0`，其余 0
方案数	`dp[0] = 1`

💡 记住：动态规划就是填表。想清楚 dp 数组的含义和转移方程，剩下就是写循环、填表格。23 道题吃透，DP 的大门就彻底打开了。加油！

动态规划入门：把大问题拆成小问题，一步一步解

一、什么是动态规划？

从斐波那契数列说起

DP 三个关键特征

DP 和贪心的区别

DP 解题四步法

二、例题精讲

第一类：入门递推 —— 从简单填表开始

例9.2 数字金字塔 —— "从下往上，逐层递推"

第二类：DAG 最短路 / 最长路 —— "沿着箭头，一站一站推"

例9.5 城市交通路网 —— "从起点到终点，找最省钱的路线"

例9.6 挖地雷 —— "沿着地道，挖最多的雷"

第三类：LIS/LCS 子序列系列 —— "一串接一串"

例9.3 最长不下降序列（LIS）—— "一条链串到底"

例9.4 拦截导弹（NOIP1999）—— "一套系统一条下降链"

例9.7 友好城市 —— "排序后就是 LIS"

例9.8 合唱队形 —— "先上升再下降，中间最高"

例9.9 最长公共子序列（LCS）—— "找两个字符串的公共基因"

第四类：背包九讲精选 —— "装与不装的智慧"

例9.11 01背包问题 —— "要么拿，要么不拿"

例9.12 完全背包问题 —— "想拿几个拿几个"

例9.13 庆功会（多重背包）—— "每样最多拿 s 件"

例9.14 混合背包 —— "三种背包一锅烩"

例9.15 潜水员（二维费用背包）—— "两种气体都要够"

例9.16 分组背包 —— "每组最多选一件"

例9.17 货币系统 —— "凑钱有多少种方案"

例9.10 机器分配 —— "M 台设备分给 N 个公司"

第五类：区间 / 划分 DP —— "从短到长，枚举分界点"

例9.18 合并石子（区间 DP）—— "一层层合并，从短到长"

例9.19 乘积最大 —— "K 个乘号，怎么插最划算"

例9.20 编辑距离 —— "最少几步把 A 变成 B"

例9.21 方格取数 —— "走两次，一起走"

例9.22 复制书稿 —— "M 本书分给 K 个人，连续分配"

例9.23 橱窗布置 —— "花束顺序插花瓶，最美搭配"

第六类：记忆化搜索 —— "滑到哪里，记到哪里"

例9.24 滑雪 —— "DFS + 缓存 = 记忆化搜索"

三、23 题总表

DP 题型分类速查

DP 解题四步法（再强调）

DP 常见初始化套路

状态

开发

支持

还没有账户？

登录