J-L28 动态规划入门¶

覆盖词条：KJ-37a~d ｜先修：J-L24/L25/L09

线性递推与一维 DP¶

台阶问题¹¶

台阶问题

题目描述

有 \(N\) 级台阶，你一开始在底部，每次可以向上迈 \(1 \sim K\) 级台阶，问到达第 \(N\) 级台阶有多少种不同方式（结果对 \(100003\) 取模）。

输入格式

两个正整数 \(N, K\)。

输出格式

一个正整数，为方案数对 \(100003\) 取模的结果。

样例输入

5 2

样例输出

数据范围

\(1 \le N \le 10^5\)，\(1 \le K \le 100\)

台阶问题 AC 代码

解题思路

枚举最后一步迈的级数 \(j\ (1 \le j \le K)\)，则 \(f_i = \sum_{j=1}^{K} f_{i-j}\)，边界 \(f_0 = 1\)。这是爬楼梯的 K 阶推广。

AC代码

#include <bits/stdc++.h>
using namespace std;

const int MOD = 100003;

int main() {
    int n, k;
    cin >> n >> k;
    vector<long long> f(n + 1);
    f[0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= min(k, i); j++)   // 枚举最后一步迈的级数
            f[i] = (f[i] + f[i - j]) % MOD;
    cout << f[n] << "\n";
    return 0;
}

最大子段和²¶

最大子段和

题目描述

给出一个长度为 \(n\) 的序列 \(a\)，选出其中连续且非空的一段使得这段和最大。

输入格式

第一行是一个整数，表示序列的长度 \(n\)。第二行有 \(n\) 个整数，第 \(i\) 个整数表示序列的第 \(i\) 个数字 \(a_i\)。

输出格式

输出一行一个整数表示答案。

样例输入

1 2	`7 2 -4 3 -1 2 -4 3`

样例输出

（选取 \([3,5]\) 子段 \(\{3,-1,2\}\)，其和为 4。）

数据范围

\(1 \le n \le 2 \times 10^5\)
\(-10^4 \le a_i \le 10^4\)

最大子段和 AC 代码

解题思路

\(dp_i = \max(a_i,\ dp_{i-1} + a_i)\)：以前一项结尾的子段如果贡献为负，就舍弃前缀、从 \(a_i\) 重新开始；过程中取全局最大值。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int best = INT_MIN, cur = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cur = max(x, cur + x);                 // 前缀为负则从自己重新开始
        best = max(best, cur);
    }
    cout << best << "\n";
    return 0;
}

摆花³¶

摆花

题目描述

花店门口要摆上一排花，共 \(m\) 盆。顾客最喜欢的花有 \(n\) 种，从 1 到 \(n\) 标号。规定第 \(i\) 种花不能超过 \(a_i\) 盆，摆花时同一种花放在一起，且不同种类的花需按标号从小到大的顺序依次摆列。求一共有多少种不同的摆花方案（对 \(10^6+7\) 取模）。

输入格式

第一行包含两个正整数 \(n\) 和 \(m\)。第二行有 \(n\) 个整数，依次表示 \(a_1, a_2, \cdots, a_n\)。

输出格式

一个整数，表示方案数对 \(10^6+7\) 取模的结果。

样例输入

1
2

2 4
3 2

样例输出

数据范围

\(1 \le n, m \le 100\)，\(1 \le a_i \le 100\)

摆花 AC 代码

解题思路

同种相邻 + 编号有序，等价于：第 \(i\) 种花选 \(c_i\) 盆（\(0 \le c_i \le a_i\)），且 \(\sum c_i = m\)。设 \(dp_{i,j}\) 为前 \(i\) 种花摆 \(j\) 盆的方案数，转移 \(dp_{i,j} = \sum_{k=0}^{a_i} dp_{i-1,j-k}\)。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    dp[0][0] = 1;                              // 什么花都不摆：1 种方案
    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a[i];
        for (int j = 0; j <= m; j++)
            for (int k = 0; k <= min(a[i], j); k++)   // 第 i 种花摆 k 盆
                dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % 1000007;
    }
    cout << dp[n][m] << "\n";
    return 0;
}

传球游戏⁴¶

传球游戏

题目描述

\(n\) 个同学站成一个圆圈，其中一个同学（1 号）手里拿着球，每次传球可以传给左右两个同学中的一个。传了 \(m\) 次后，球又回到 1 号手里的传球方法有多少种？

输入格式

一行两个整数 \(n, m\)。

输出格式

一个整数，表示符合题意的方法数。

样例输入

3 3

样例输出

数据范围

\(3 \le n \le 30\)，\(1 \le m \le 30\)

传球游戏 AC 代码

解题思路

设 \(dp_{i,j}\) 为传 \(i\) 次球在 \(j\) 号手中的方案数，则 \(dp_{i,j} = dp_{i-1,j-1} + dp_{i-1,j+1}\)（环形邻居，两端特判）。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<long long>> dp(m + 1, vector<long long>(n + 1, 0));
    dp[0][1] = 1;                              // 第 0 次时球在 1 号手中
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) {
            int left = (j == 1 ? n : j - 1);   // 环形邻居特判两端
            int right = (j == n ? 1 : j + 1);
            dp[i][j] = dp[i - 1][left] + dp[i - 1][right];
        }
    cout << dp[m][1] << "\n";
    return 0;
}

杂务⁵¶

杂务

题目描述

John 的农场有 \(n\) 项杂务，第 \(i\) 项需要 \(len_i\) 时间，且可能依赖若干项更早编号的杂务（编号 \(k\) 的准备工作只可能在 \(1 \sim k-1\) 中）。互相无关的杂务可以同时进行。求完成所有杂务的最短时间。

输入格式

第 1 行一个整数 \(n\)。接下来 \(n\) 行，每行依次是：工作序号、所需时间 \(len\)、若干个必须完成的准备工作编号（以 0 结束）。

输出格式

一个整数，表示完成所有杂务所需的最短时间。

样例输入

样例输出

数据范围

\(3 \le n \le 10^4\)，\(1 \le len \le 100\)，前驱总数不超过 100

杂务 AC 代码

解题思路

杂务 \(k\) 的前驱只在 \(1 \sim k-1\)，读入顺序即拓扑序：\(finish_i = \max(finish_{\text{前驱}}) + len_i\)——任务可并发，所以前驱取 max 而不是求和。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> finish(n + 1, 0);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int idx, len, pre;
        cin >> idx >> len;
        int start = 0;
        while (cin >> pre && pre)              // 杂务 k 的前驱只在 1..k-1，读入序即拓扑序
            start = max(start, finish[pre]);   // 可并发：取前驱完成时间的最大值
        finish[i] = start + len;
        ans = max(ans, finish[i]);
    }
    cout << ans << "\n";
    return 0;
}

挖地雷⁶¶

挖地雷

题目描述

地图上有 \(N\) 个地窖，每个地窖埋有一定数量的地雷，并给出地窖之间的连接路径。某人可以从任一地窖出发，每次移动到一个编号比当前大且连通的地窖，直到无路可走。设计路线使挖到的地雷最多，输出路线与最大地雷数。

输入格式

第 1 行一个整数 \(N\)；第 2 行 \(N\) 个数表示各地窖的地雷数；第 3 至第 \(N+1\) 行为上三角邻接矩阵（0/1 表示有无路径）。

输出格式

第一行输出挖地雷顺序（空格分隔）；第二行输出最大地雷数。

样例输入

样例输出

1 2	`1 3 4 5 27`

数据范围

\(N \le 20\)，每窖地雷数不超过 300

挖地雷 AC 代码

解题思路

编号递增 ⇒ 图是 DAG，按编号递推：\(f_i = a_i + \max_{j<i,\ 有边} f_j\)，用 \(pre\) 数组记录前驱，从终点回溯还原路径。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n + 1), f(n + 1), pre(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<vector<bool>> e(n + 1, vector<bool>(n + 1, false));
    for (int i = 1; i < n; i++)
        for (int j = i + 1; j <= n; j++) {
            int x;
            cin >> x;
            e[i][j] = x;                       // 上三角邻接矩阵，编号递增的有向边
        }
    int best = 0, endPos = 1;
    for (int i = 1; i <= n; i++) {
        f[i] = a[i];
        for (int j = 1; j < i; j++)
            if (e[j][i] && f[j] + a[i] > f[i]) {
                f[i] = f[j] + a[i];
                pre[i] = j;                    // 记录前驱用于还原路径
            }
        if (f[i] > best) { best = f[i]; endPos = i; }
    }
    vector<int> path;
    for (int i = endPos; i; i = pre[i]) path.push_back(i);
    for (int k = (int)path.size() - 1; k >= 0; k--) cout << path[k] << " \n"[k == 0];
    cout << best << "\n";
    return 0;
}

覆盖墙壁⁷¶

覆盖墙壁

题目描述

用 \(2 \times 1\) 的砖和 L 型覆盖 3 个单元的砖（可旋转）铺满 \(2 \times N\) 的墙壁，求方案数的末 4 位。

输入格式

一个整数 \(N\)。

输出格式

覆盖方法数的末 4 位（不足 4 位直接输出）。

样例输入

样例输出

数据范围

\(1 \le N \le 10^6\)

覆盖墙壁 AC 代码

解题思路

一个状态不够就造辅助状态：\(F_i\) 为铺满 \(2 \times i\) 的方案数，\(G_i\) 为「铺满 \(2 \times (i+1)\) 但缺一角」的方案数。转移 \(F_i = F_{i-1} + F_{i-2} + 2G_{i-2}\)，\(G_i = F_{i-1} + G_{i-1}\)，对 10000 取模。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> F(n + 2, 0), G(n + 2, 0);
    F[0] = 1;                                  // F[i]：铺满 2×i 的方案数
    G[0] = 0;                                  // G[i]：铺满 2×(i+1) 且缺一角的方案数
    if (n >= 1) { F[1] = 1; G[1] = 1; }
    for (int i = 2; i <= n; i++) {
        F[i] = (F[i - 1] + F[i - 2] + 2 * G[i - 2]) % 10000;
        G[i] = (F[i - 1] + G[i - 1]) % 10000;
    }
    cout << F[n] << "\n";
    return 0;
}

网格递推¶

数字三角形⁸¶

数字三角形

题目描述

一个 \(r\) 行的数字金字塔，第 \(i\) 行有 \(i\) 个数。从塔顶出发，每一步可以走到下一行相邻的两个数之一（左下或右下），一直走到塔底。把沿途经过的数全部加起来，最大能是多少？

输入格式

第一行一个整数 \(r\)；接下来 \(r\) 行，第 \(i\) 行有 \(i\) 个整数。

输出格式

一行一个整数，最大路径和。

样例输入

样例输出

（路径 1 → 3 → 6 → 10。）

数据范围

\(1 \le r \le 1000\)
矩阵中的数在 \(0 \sim 100\) 之间

数字三角形 AC 代码

解题思路

自底向上 DP：\(dp_j\) 为从当前位置走到塔底的最大和，转移 \(dp_j = a_{i,j} + \max(dp_j, dp_{j+1})\)（左下 / 右下取较优）；答案为塔顶 \(dp_0\)。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int r;
    cin >> r;
    vector<vector<int>> a(r, vector<int>(r));
    for (int i = 0; i < r; i++)
        for (int j = 0; j <= i; j++) cin >> a[i][j];
    vector<int> dp = a[r - 1];             // 自底向上，dp[j] = 从 (i,j) 到底部的最大和
    for (int i = r - 2; i >= 0; i--)
        for (int j = 0; j <= i; j++)
            dp[j] = a[i][j] + max(dp[j], dp[j + 1]);
    cout << dp[0] << "\n";
    return 0;
}

过河卒⁹¶

过河卒

题目描述

棋盘上 \(A\) 点 \((0,0)\) 有一个过河卒，需要走到目标 \(B\) 点 \((n,m)\)。卒只能向下或向右走。棋盘上 \(C\) 点有一个马，马所在的位置和所有跳跃一步可达的点称为马的控制点，卒不能通过控制点。求卒从 \(A\) 到 \(B\) 的路径条数。

输入格式

一行四个整数，分别表示 \(B\) 点坐标和马的坐标。

输出格式

一个整数，表示所有的路径条数。

样例输入

6 6 3 3

样例输出

数据范围

\(1 \le n, m \le 20\)，\(0 \le\) 马的坐标 \(\le 20\)
保证起点不是马的控制点

过河卒 AC 代码

解题思路

网格计数 DP：\(f_{i,j} = f_{i-1,j} + f_{i,j-1}\)，马控点方案数置 0。三连坑：马控点包含马自身；坐标整体 +2 防止越界；路径数要开 long long。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n, m, cx, cy;
    cin >> n >> m >> cx >> cy;
    n += 2; m += 2; cx += 2; cy += 2;          // 坐标整体 +2，防止马控点为负越界
    vector<vector<long long>> f(n + 1, vector<long long>(m + 1, 0));
    vector<vector<bool>> blocked(n + 1, vector<bool>(m + 1, false));
    blocked[cx][cy] = true;
    int dx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
    int dy[8] = {2, -2, 2, -2, 1, -1, 1, -1};
    for (int k = 0; k < 8; k++) {
        int x = cx + dx[k], y = cy + dy[k];
        if (x >= 0 && x <= n && y >= 0 && y <= m) blocked[x][y] = true;
    }
    f[2][1] = 1;                               // 原点 (0,0) 偏移后在 (2,2)，借左侧种子转移
    for (int i = 2; i <= n; i++)
        for (int j = 2; j <= m; j++) {
            if (blocked[i][j]) continue;       // 马控点不可通行，方案数置 0
            f[i][j] = f[i - 1][j] + f[i][j - 1];
        }
    cout << f[n][m] << "\n";
    return 0;
}

背包 DP¶

采药¹⁰¶

采药

题目描述

山洞里有 \(M\) 株草药，采第 \(i\) 株需要 \(t_i\) 时间、价值 \(v_i\)。你总共只有 \(T\) 个单位时间，每株草药最多采一次。在规定时间内能采到的草药最大总价值是多少？

输入格式

第一行两个整数 \(T, M\)；接下来 \(M\) 行，每行两个整数 \(t_i, v_i\)。

输出格式

一行一个整数，最大总价值。

样例输入

样例输出

数据范围

\(1 \le T \le 1000\)
\(1 \le M \le 100\)
\(1 \le t_i, v_i \le 100\)

采药 AC 代码

解题思路

0/1 背包：设 dp[j] 为时间 \(j\) 内能获得的最大价值，逐株草药转移 dp[j] = max(dp[j], dp[j-t] + v)；容量倒序循环保证每株草药最多采一次，答案为 dp[T]。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T, M;
    cin >> T >> M;
    vector<int> dp(T + 1, 0);              // dp[j] = 时间 j 内能采到的最大价值
    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] << "\n";
    return 0;
}

装箱问题¹¹¶

装箱问题

题目描述

有一个箱子容量为 \(V\)，同时有 \(n\) 个物品，每个物品有一个体积。现在从 \(n\) 个物品中任取若干个装入箱内（也可以不取），使箱子的剩余空间最小。输出这个最小值。

输入格式

第一行一个整数 \(V\)；第二行一个整数 \(n\)；接下来 \(n\) 行，每行一个正整数表示物品体积。

输出格式

一行一个整数，表示箱子最小剩余空间。

样例输入

样例输出

（取 8+9+7 恰好装满。）

数据范围

\(V \le 20000\)，\(n \le 30\)，物品体积为正整数

装箱问题 AC 代码

解题思路

体积当价值跑 0/1 背包，\(dp_j\) 为容量 \(j\) 能装的最大体积，答案为 \(V - dp_V\)——背包建模时「价值」需要自己构造。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int V, n;
    cin >> V >> n;
    vector<int> dp(V + 1, 0);                  // dp[j] = 容量 j 能装的最大体积（体积即价值）
    for (int i = 0; i < n; i++) {
        int w;
        cin >> w;
        for (int j = V; j >= w; j--)
            dp[j] = max(dp[j], dp[j - w] + w);
    }
    cout << V - dp[V] << "\n";                 // 最小剩余 = V - 最大可装体积
    return 0;
}

疯狂的采药¹²¶

疯狂的采药

题目描述

与采药完全相同，唯一的区别是：每种草药可以无限制地疯狂采摘，且草药种类和采药时间都变多了。求规定时间内能采到的草药最大总价值。

输入格式

第一行两个整数 \(t, m\)；接下来 \(m\) 行，每行两个整数 \(a_i, b_i\)，分别表示采摘第 \(i\) 种草药的时间和价值。

输出格式

一行一个整数，最大总价值。

样例输入

样例输出

（70 个时间全采第三种草药，价值 2 × 70。）

数据范围

\(1 \le m \le 10^4\)，\(1 \le t \le 10^7\)，且 \(1 \le m \times t \le 10^7\)
\(1 \le a_i, b_i \le 10^4\)

疯狂的采药 AC 代码

解题思路

完全背包：与采药（0/1 背包）只差容量循环方向——正序循环时 \(f_{j-a}\) 可能已包含本种草药，相当于无限采。答案上限约 \(10^{11}\)，必须 long long。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t, m;
    cin >> t >> m;
    vector<long long> f(t + 1, 0);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        for (int j = a; j <= t; j++)           // 正序：每种草药可无限采（完全背包）
            f[j] = max(f[j], f[j - a] + b);
    }
    cout << f[t] << "\n";                      // 价值上限约 1e11，必须 long long
    return 0;
}

纸币问题 1¹³¶

纸币问题 1

题目描述

某国有 \(n\) 种纸币，每种纸币面额为 \(a_i\) 并且有无限张，现在要凑出 \(w\) 的金额，试问最少用多少张纸币可以凑出来（保证可以凑出）。

输入格式

第一行两个整数 \(n, w\)；第二行 \(n\) 个整数 \(a_i\)。

输出格式

一行一个整数，表示最少使用的纸币张数。

样例输入

1 2	`6 3 1 2 5`

样例输出

（一张 5 加一张 1。）

数据范围

\(1 \le n \le 10^3\)，\(1 \le a_i, w \le 10^4\)

纸币问题 1 AC 代码

解题思路

min 型完全背包：\(f_v = \min(f_{v-a_i}) + 1\)，初值设极大值、\(f_0 = 0\)——背包不只求 max，min 型与计数型同样常见。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, w;
    cin >> n >> w;
    vector<int> a(n);
    for (auto& x : a) cin >> x;
    vector<int> f(w + 1, 1e9);
    f[0] = 0;                                  // 凑出 0 元需要 0 张纸币
    for (int i = 1; i <= w; i++)
        for (int v : a)
            if (i >= v) f[i] = min(f[i], f[i - v] + 1);
    cout << f[w] << "\n";                      // 题目保证有解
    return 0;
}

小 A 点菜¹⁴¶

小 A 点菜

题目描述

uim 指着价目表说「随便点」，但口袋里只剩 \(M\) 元。餐厅有 \(N\) 道菜，第 \(i\) 道菜价格为 \(a_i\)。点菜必须恰好把 \(M\) 元全部花完，求点菜方案数。

输入格式

第一行两个整数 \(N, M\)；第二行 \(N\) 个正整数 \(a_i\)（可能有重复）。

输出格式

一个正整数，表示点菜方案数。

样例输入

1 2	`5 10 2 3 5 8 10`

样例输出

（{2,8}、{2,3,5}、{10} 三种点法。）

数据范围

\(N \le 100\)，\(M \le 10^4\)

小 A 点菜 AC 代码

解题思路

计数型 0/1 背包（恰好装满）：\(f_0 = 1\) 是「空方案」种子，转移 \(f_j \mathrel{+}= f_{j-a_i}\)（倒序保证每道菜最多点一次）。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<int> f(m + 1, 0);
    f[0] = 1;                                  // 一道菜都不点、恰好 0 元：1 种方案
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= a[i]; j--)        // 倒序：每道菜最多点一次
            f[j] += f[j - a[i]];
    cout << f[m] << "\n";
    return 0;
}

货币系统¹⁵¶

货币系统

题目描述

货币系统由 \(V\) 种面值组成，每种面值无限张。求用这些货币构造出面值 \(N\) 的方案数（保证在 64 位整数范围内）。

输入格式

第一行两个整数 \(V, N\)；第二行 \(V\) 个整数表示面值。

输出格式

一行一个整数，代表方案数。

样例输入

1 2	`3 10 1 2 5`

样例输出

数据范围

\(1 \le V \le 25\)，\(1 \le N \le 10^4\)

货币系统 AC 代码

解题思路

计数型完全背包，与小 A 点菜成对辨析：面值正序循环 = 每种面值无限张，\(f_j \mathrel{+}= f_{j-c}\)，\(f_0 = 1\)，开 long long。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int v, n;
    cin >> v >> n;
    vector<long long> f(n + 1, 0);
    f[0] = 1;
    for (int i = 0; i < v; i++) {
        int c;
        cin >> c;
        for (int j = c; j <= n; j++)           // 正序：每种面值无限张
            f[j] += f[j - c];
    }
    cout << f[n] << "\n";                      // 题目保证在 64 位范围内
    return 0;
}

通天之分组背包¹⁶¶

通天之分组背包

题目描述

物品分为 \(k\) 组，每组中的物品相互冲突（至多选一件）。背包最大承重为 \(m\)，求最大的利用价值。

输入格式

两个数 \(m, n\)；接下来 \(n\) 行，每行三个数 \(a_i, b_i, c_i\)，表示物品的重量、价值、所属组数。

输出格式

一个数，最大的利用价值。

样例输入

样例输出

（第 1 组选 (5,10)、第 2 组选 (4,6)，总重 9、价值 16。）

数据范围

\(0 \le m \le 1000\)，\(1 \le n \le 1000\)，\(1 \le k \le 100\)

通天之分组背包 AC 代码

解题思路

三循环顺序是全部考点：组外层 → 容量倒序 → 组内物品。顺序错了组内互斥就会失效。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int m, n;
    cin >> m >> n;
    vector<int> w(n + 1), v(n + 1), g(n + 1);
    int K = 0;
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i] >> g[i];
        K = max(K, g[i]);
    }
    vector<vector<int>> items(K + 1);
    for (int i = 1; i <= n; i++) items[g[i]].push_back(i);
    vector<int> dp(m + 1, 0);
    for (int k = 1; k <= K; k++)               // 组外层
        for (int j = m; j >= 0; j--)           // 容量倒序
            for (int i : items[k])             // 组内物品：每组至多选一件
                if (j >= w[i]) dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    cout << dp[m] << "\n";
    return 0;
}

宝物筛选¹⁷¶

宝物筛选

题目描述

洞穴里有 \(n\) 种宝物，第 \(i\) 种价值 \(v_i\)、重量 \(w_i\)、有 \(m_i\) 件。采集车最大载重 \(W\)，在不超载的前提下选择一些宝物装车，使价值和最大。

输入格式

第一行两个整数 \(n, W\)；接下来 \(n\) 行，每行三个整数 \(v_i, w_i, m_i\)。

输出格式

一个整数，表示能收集的最大价值。

样例输入

1
2
3

2 10
3 2 2
5 3 3

样例输出

数据范围

\(\sum m_i \le 10^5\)，\(W \le 4 \times 10^4\)，\(n \le 100\)
\(1 \le w_i, v_i \le 1000\)

宝物筛选 AC 代码

解题思路

多重背包：朴素 \(O(W\sum m)\) 必超时。二进制拆分——把 \(m_i\) 件拆成 \(1, 2, 4, \dots\) 与余数若干「包裹」（可拼出 \(0 \sim m_i\) 的任意件数），再对包裹跑 0/1 背包，件数降为 \(O(\log m_i)\)。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, W;
    cin >> n >> W;
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < n; i++) {
        int v, w, m;
        cin >> v >> w >> m;
        for (int k = 1; k <= m; m -= k, k <<= 1) {   // 二进制拆分：1,2,4,...,余数
            int cnt = min(k, m);                     // 每个包裹覆盖 0..m 的任意件数组合
            for (int j = W; j >= cnt * w; j--)       // 拆成的包裹做 0/1 背包
                dp[j] = max(dp[j], dp[j - cnt * w] + cnt * v);
        }
    }
    cout << dp[W] << "\n";
    return 0;
}

子序列与双串 DP¶

最长上升子序列 LIS¹⁸¶

最长上升子序列

题目描述

给出一个由 \(n\) 个不超过 \(10^6\) 的正整数组成的序列，请输出这个序列的最长上升子序列的长度（按原顺序取出若干个数，逐渐增大，不要求连续）。

输入格式

第一行一个整数 \(n\)；第二行 \(n\) 个整数。

输出格式

一个整数表示答案。

样例输入

1 2	`6 1 7 3 5 9 4`

样例输出

（如 1 → 3 → 5 → 9。）

数据范围

\(1 \le n \le 5000\)
序列中的数不超过 \(10^6\)

LIS AC 代码（DP）

解题思路

设 \(f_i\) 为以 \(a_i\) 结尾的 LIS 长度，转移 \(f_i = \max_{j<i,\ a_j<a_i}(f_j + 1)\)，边界 \(f_i = 1\)；答案是全表最大值而不是 \(f_n\)。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n), f(n, 1);                 // f[i] = 以 a[i] 结尾的最长上升子序列长度
    for (auto& x : a) cin >> x;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < i; j++)
            if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
    cout << *max_element(f.begin(), f.end()) << "\n";   // 答案是全表最大值
    return 0;
}

补充解法：贪心 + 二分 \(O(n\log n)\)

解题思路

tail[k] 维护「长度为 \(k+1\) 的上升子序列的最小结尾」；每个新数用 lower_bound 找到第一个 \(\ge\) 它的位置替换（没有则追加），tail 的最终长度即答案。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n), tail;                    // tail[k] = 长度 k+1 的上升子序列的最小结尾
    for (auto& x : a) cin >> x;
    for (int x : a) {
        auto it = lower_bound(tail.begin(), tail.end(), x);   // 严格上升用 lower_bound
        if (it == tail.end()) tail.push_back(x);
        else *it = x;
    }
    cout << tail.size() << "\n";
    return 0;
}

编辑距离¹⁹¶

编辑距离

题目描述

设 \(A\) 和 \(B\) 是两个字符串（只含小写字母）。用最少的字符操作次数将 \(A\) 转换为 \(B\)，操作有三种：删除一个字符、插入一个字符、将一个字符改为另一个字符。

输入格式

第一行为字符串 \(A\)；第二行为字符串 \(B\)。

输出格式

一个正整数，为最少字符操作次数。

样例输入

1 2	`kitten sitting`

样例输出

（k→s、e→i，再插入 g。）

数据范围

\(1 \le |A|, |B| \le 2000\)

编辑距离 AC 代码

解题思路

双串 DP：\(f_{i,j}\) 为 \(A\) 前 \(i\) 个字符变成 \(B\) 前 \(j\) 个字符的最少操作数，转移取「删 / 插 / 改（或不动）」三者最小；边界 \(f_{i,0}=i\)、\(f_{0,j}=j\)。CSP-J 2023 完善程序原型。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size();
    vector<vector<int>> f(n + 1, vector<int>(m + 1));
    for (int i = 0; i <= n; i++) f[i][0] = i;  // 边界：A 前 i 个字符全删掉
    for (int j = 0; j <= m; j++) f[0][j] = j;  // 边界：插入 j 个字符
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            f[i][j] = min(min(f[i - 1][j] + 1, f[i][j - 1] + 1),   // 删 / 插
                          f[i - 1][j - 1] + (a[i - 1] != b[j - 1])); // 改 / 不动
    cout << f[n][m] << "\n";
    return 0;
}

两个排列的 LCS²⁰¶

两个排列的最长公共子序列

题目描述

给出 \(1,2,\ldots,n\) 的两个排列 \(P_1\) 和 \(P_2\)，求它们的最长公共子序列的长度。

输入格式

第一行一个数 \(n\)；接下来两行，每行为 \(1 \sim n\) 的一个排列。

输出格式

一个数，即最长公共子序列的长度。

样例输入

1
2
3

5
3 2 1 4 5
1 2 3 4 5

样例输出

数据范围

对于 50% 的数据，\(n \le 10^3\)（可 \(O(n^2)\) 求 LCS）
对于 100% 的数据，\(n \le 10^5\)

DP 解法：仅通过前 50% 数据

解题思路

双串 DP：\(f_{i,j}\) 为 \(P_1\) 前 \(i\) 个数与 \(P_2\) 前 \(j\) 个数的 LCS 长度——末位相等则 \(f_{i,j} = f_{i-1,j-1} + 1\)，否则 \(f_{i,j} = \max(f_{i-1,j}, f_{i,j-1})\)。\(O(n^2)\) 只能通过前 50% 数据（\(n \le 10^3\)）。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    vector<vector<int>> f(n + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            f[i][j] = (a[i] == b[j]) ? f[i - 1][j - 1] + 1   // 末位配对
                                     : max(f[i - 1][j], f[i][j - 1]); // 删一边
    cout << f[n][n] << "\n";
    return 0;
}

补充解法：排列转化 + LIS \(O(n\log n)\)，可过 100% 数据

解题思路

两串都是排列（无重复值）：把 \(P_1\) 的每个值替换成它在 \(P_2\) 中的位置，LCS 就变成了新序列的 LIS，二分做到 \(O(n \log n)\)。「不会做的题转化成会做的题」的代表作。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> p1(n + 1), pos(n + 1);
    for (int i = 1; i <= n; i++) cin >> p1[i];
    for (int j = 1; j <= n; j++) {
        int x;
        cin >> x;
        pos[x] = j;                            // 记录 P2 中每个值的出现位置
    }
    vector<int> tail;
    for (int i = 1; i <= n; i++) {
        int v = pos[p1[i]];                    // LCS 转化为对映射序列求 LIS
        auto it = lower_bound(tail.begin(), tail.end(), v);
        if (it == tail.end()) tail.push_back(v);
        else *it = v;
    }
    cout << tail.size() << "\n";
    return 0;
}

导弹拦截²¹¶

导弹拦截

题目描述

一套导弹拦截系统第一发能到任意高度，但以后每一发都不能高于前一发。输入导弹依次飞来的高度，问：这套系统最多能拦截多少导弹；要拦截所有导弹，最少要配备多少套这种系统。

输入格式

一行，若干个整数，中间由空格隔开。

输出格式

两行，每行一个整数：第一行为最多拦截的导弹数；第二行为最少需要配备的系统数。

样例输入

1	`389 207 155 300 299 170 158 65`

样例输出

1
2

6
2

数据范围

导弹个数不超过 \(10^5\)（后 50% 数据需 \(O(n\log n)\)）
导弹高度为不超过 \(5 \times 10^4\) 的正整数

DP 解法：仅通过前 50% 数据

解题思路

两问都是 LIS 型 DP：第一问最长不升子序列，\(f_i = \max_{j<i,\ h_j \ge h_i}(f_j+1)\)；第二问由 Dilworth 定理，最少系统数 = 最长严格上升子序列长度，\(g_i = \max_{j<i,\ h_j < h_i}(g_j+1)\)。\(O(n^2)\) 只能通过前 50% 数据（\(n \le 10^4\)）。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> h;
    int x;
    while (cin >> x) h.push_back(x);
    int n = h.size();
    vector<int> f(n, 1), g(n, 1);              // f: 最长不升（第一问）；g: 最长严格上升（第二问）
    int ans1 = 0, ans2 = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (h[j] >= h[i]) f[i] = max(f[i], f[j] + 1);   // 不升子序列能接上
            if (h[j] < h[i]) g[i] = max(g[i], g[j] + 1);    // 严格上升子序列能接上
        }
        ans1 = max(ans1, f[i]);
        ans2 = max(ans2, g[i]);
    }
    cout << ans1 << "\n" << ans2 << "\n";      // Dilworth：ans2 = 最少系统数
    return 0;
}

补充解法：贪心 + 二分 \(O(n\log n)\)，可过 100% 数据

解题思路

后 50% 数据 \(n \le 10^5\)，\(O(n^2)\) 不够：两个方向各维护一个 tail 数组——不升方向用 upper_bound(greater)、严格上升方向用 lower_bound 找替换位置。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> h;
    int x;
    while (cin >> x) h.push_back(x);
    vector<int> down, up;                      // down: 最长不升 tail；up: 最长严格上升 tail
    for (int v : h) {
        auto it1 = upper_bound(down.begin(), down.end(), v, greater<int>());
        if (it1 == down.end()) down.push_back(v);   // 第一问：最长不升子序列
        else *it1 = v;
        auto it2 = lower_bound(up.begin(), up.end(), v);
        if (it2 == up.end()) up.push_back(v);  // 第二问（Dilworth）：最长上升子序列
        else *it2 = v;
    }
    cout << down.size() << "\n" << up.size() << "\n";
    return 0;
}

记忆化搜索与综合¶

滑雪²²¶

滑雪

题目描述

二维区域中每个数代表点的高度。一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度会减小。求区域中最长的滑坡长度。

输入格式

第一行为行数 \(R\) 和列数 \(C\)；接下来 \(R\) 行，每行 \(C\) 个数表示高度。

输出格式

输出区域中最长滑坡的长度。

样例输入

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

样例输出

（滑坡 25 → 24 → 23 → … → 1。）

数据范围

\(1 \le R, C \le 100\)
高度为不超过 \(10^4\) 的整数

滑雪 AC 代码

解题思路

记忆化搜索：裸 DFS 会重复计算大量子问题，加一个 memo 数组存「从 \((i,j)\) 出发的最长滑距」即可。高度递减天然无环，不需要 visited 数组——J-L26 的 DFS 加一个数组就是 DP。

AC代码

#include <bits/stdc++.h>
using namespace std;

int R, C;
vector<vector<int>> h, memo;

// 从 (x,y) 出发能滑行的最长长度（高度严格下降）
int dfs(int x, int y) {
    int& res = memo[x][y];
    if (res) return res;                       // 记忆化：算过直接返回
    res = 1;                                   // 答案包含该点自身
    int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k], ny = y + dy[k];
        if (nx >= 1 && nx <= R && ny >= 1 && ny <= C && h[nx][ny] < h[x][y])
            res = max(res, dfs(nx, ny) + 1);   // 高度递减天然无环，无需 visited
    }
    return res;
}

int main() {
    cin >> R >> C;
    h.assign(R + 1, vector<int>(C + 1));
    memo.assign(R + 1, vector<int>(C + 1, 0));
    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 << "\n";
    return 0;
}

纪念品²³¶

纪念品

题目描述

小伟知道未来 \(T\) 天 \(N\) 种纪念品每天的价格。每天可以无限次买入或卖出纪念品（当日买的可以当日卖，当日卖出换回的金币可立即使用），\(T\) 天后必须全部卖出。初始有 \(M\) 枚金币，求最多能拥有多少金币。

输入格式

第一行三个正整数 \(T, N, M\)；接下来 \(T\) 行，每行 \(N\) 个整数表示第 \(i\) 天各种纪念品的价格 \(P_{i,j}\)。

输出格式

一个正整数，表示最多能拥有的金币数量。

样例输入

1
2
3

2 1 10
5
10

样例输出

（第一天花 10 枚买 2 个纪念品，第二天卖出得 20 枚。）

数据范围

\(T, N \le 100\)，\(M \le 10^3\)
\(1 \le P_{i,j} \le 10^4\)

纪念品 AC 代码

解题思路

关键转化：「当日买入可当日卖出」⇒ 连续持有若干天 = 每天卖掉再买回，因此不需要记录持有状态。相邻两天之间跑一次完全背包（每件纪念品成本 \(P_{d,j}\)、收益 \(P_{d+1,j} - P_{d,j}\)），每天结束取最大金币数进入下一天。CSP-J 2019 T3。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T, N, M;
    cin >> T >> N >> M;
    vector<vector<int>> p(T + 1, vector<int>(N + 1));
    for (int i = 1; i <= T; i++)
        for (int j = 1; j <= N; j++) cin >> p[i][j];
    int ans = M;
    for (int d = 1; d < T; d++) {              // 相邻两天之间跑一次完全背包
        vector<int> dp(M + 1, 0);
        dp[ans] = ans;                         // 今天不买：明天仍是 ans
        for (int j = 1; j <= N; j++) {
            int w = p[d][j], gain = p[d + 1][j] - w;
            if (gain <= 0) continue;           // 不涨价的纪念品没有交易价值
            for (int k = w; k <= M; k++)       // 正序：当日可反复买卖（完全背包）
                dp[k] = max(dp[k], dp[k - w] + w + gain);
        }
        ans = *max_element(dp.begin(), dp.end());
    }
    cout << ans << "\n";
    return 0;
}

模板与代码¶

各范式的通用模板已嵌入上方典型题。作业题与更多变式（开心的金明、5 倍经验日、传球之外的环形/计数变式、低价购买、鸡蛋掉落等）见题单 tools/题单库/动态规划入门。

线性递推（K 阶） · 洛谷 P1192。 ↩
线性 DP（max 决策） · 洛谷 P1115。 ↩
计数 DP · 洛谷 P1077 · NOIP2012。 ↩
环形计数 DP · 洛谷 P1057 · NOIP2008。 ↩
DAG 上 DP · 洛谷 P1113。 ↩
DAG 上 DP · 洛谷 P2196 · NOIP1996。 ↩
线性递推（双状态） · 洛谷 P1990。 ↩
网格递推 · 洛谷 P1216 · IOI1994。 ↩
网格计数 DP · 洛谷 P1002 · NOIP2002。 ↩
0/1 背包 · 洛谷 P1048 · NOIP2005。 ↩
0/1 背包（转化） · 洛谷 P1049 · NOIP2001。 ↩
完全背包 · 洛谷 P1616。 ↩
完全背包（min 型） · 洛谷 P2842。 ↩
0/1 背包（计数型） · 洛谷 P1164。 ↩
完全背包（计数型） · 洛谷 P1474 · USACO。 ↩
分组背包 · 洛谷 P1757。 ↩
多重背包（二进制拆分） · 洛谷 P1776。 ↩
LIS（DP \(O(n^2)\)） · 洛谷 B3637；补充解法为贪心 + 二分 \(O(n\log n)\)。 ↩
双串 DP（编辑距离） · 洛谷 P2758。 ↩
双串 DP（LCS，\(O(n^2)\)） · 洛谷 P1439；补充解法为排列转化 + LIS \(O(n\log n)\)（过 100% 数据）。 ↩
LIS 型 DP（不升 + Dilworth 定理，\(O(n^2)\)） · 洛谷 P1020 · NOIP1999；补充解法为贪心 + 二分 \(O(n\log n)\)（过 100% 数据）。 ↩
记忆化搜索 · 洛谷 P1434 · SHOI2002。 ↩
完全背包综合 · 洛谷 P5662 · CSP-J 2019。 ↩

J-L28 动态规划入门¶

线性递推与一维 DP¶

台阶问题1¶

最大子段和2¶

摆花3¶

传球游戏4¶

杂务5¶

挖地雷6¶

覆盖墙壁7¶

网格递推¶

数字三角形8¶

过河卒9¶

背包 DP¶

采药10¶

装箱问题11¶

疯狂的采药12¶

纸币问题 113¶

小 A 点菜14¶

货币系统15¶

通天之分组背包16¶

宝物筛选17¶

子序列与双串 DP¶

最长上升子序列 LIS18¶

编辑距离19¶

两个排列的 LCS20¶

导弹拦截21¶

记忆化搜索与综合¶

滑雪22¶

纪念品23¶

模板与代码¶

台阶问题¹¶

最大子段和²¶

摆花³¶

传球游戏⁴¶

杂务⁵¶

挖地雷⁶¶

覆盖墙壁⁷¶

数字三角形⁸¶

过河卒⁹¶

采药¹⁰¶

装箱问题¹¹¶

疯狂的采药¹²¶

纸币问题 1¹³¶

小 A 点菜¹⁴¶

货币系统¹⁵¶

通天之分组背包¹⁶¶

宝物筛选¹⁷¶

最长上升子序列 LIS¹⁸¶

编辑距离¹⁹¶

两个排列的 LCS²⁰¶

导弹拦截²¹¶

滑雪²²¶

纪念品²³¶