1
当前没有测试数据。
一、动态规划基础概念
1. 什么是动态规划
动态规划（Dynamic Programming，简称 DP）是一种通过把原问题分解为相对简单的子问题，利用子问题的解推导原问题解的算法思想。核心是记住已经算过的结果，避免重复计算，从而提升效率，是 CSP-J 入门组复赛的核心高频考点。
2. DP 问题三要素
- 状态定义：用
dp[i]或dp[i][j]表示某种含义，明确数组每个位置对应的实际意义。 - 状态转移方程：从已知子问题的结果，推导出当前问题结果的计算公式。
- 初始化与边界：最基础子问题的答案，是递推的起点。
3. 线性 DP 特点
状态转移呈线性顺序推导，通常按数组下标从小到大依次计算，是 DP 中最基础、最常考的类型，背包问题本质上也是“选/不选”决策的线性 DP。
二、经典线性 DP 模型
模型 1：数字三角形
问题描述
给定一个 n 行的数字三角形，从顶部出发，每次可以走到下一行相邻的左或右节点，求从顶部到底部的最大路径和。
状态定义
dp[i][j]：从顶部走到第 i 行第 j 列时，能获得的最大路径和。
状态转移方程
dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + a[i][j]
含义：当前位置只能从左上方或正上方走来，取两者中的较大值，加上当前位置的数字。
边界初始化
dp[1][1] = a[1][1]（起点只有一个数字）
模板代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1005;
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];
dp[1][1] = a[1][1];
for (int i = 2; 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;
}
📌 真题演练
- 入门模板题：[洛谷 P 1216 数字三角形](https://www.luogu.com.cn/problem/P1216
模型 2：最长上升子序列（LIS）
问题描述
给定一个长度为 n 的序列，求其中最长的严格上升子序列的长度（子序列元素不要求连续）。
状态定义
dp[i]：以第 i 个元素结尾的最长上升子序列的长度。
状态转移方程
dp[i] = 1 （初始值，只选自己）
dp[i] = max(dp[i], dp[j] + 1) 当 j < i 且 a[j] < a[i]
含义：枚举 i 前面所有比 a[i]小的元素 j，尝试接在 j 后面形成更长的子序列。
模板代码（O(n²) 入门版）
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1005;
int a[N], dp[N];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
int ans = 0;
for (int i = 1; i <= n; i++) {
dp[i] = 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;
}
📌 真题演练
模型 3：最长公共子序列（LCS）
问题描述
给定两个字符串 A 和 B，求它们最长的公共子序列的长度。
状态定义
dp[i][j]：字符串 A 前 i 个字符、字符串 B 前 j 个字符的最长公共子序列长度。
状态转移方程
若 A[i] == B[j]：dp[i][j] = dp[i-1][j-1] + 1
若 A[i] != B[j]：dp[i][j] = max(dp[i-1][j], dp[i][j-1])
含义：字符相等时，公共长度加 1；不等时，取去掉 A 末尾或去掉 B 末尾中的较大值。
模板代码
- 字符数组存字符串，设置让实际下标从 1 开始
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1005;
char a[N], b[N];
int dp[N][N];
int main() {
cin >> a + 1 >> b + 1;
int n = strlen(a + 1);
int m = strlen(b + 1);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i] == b[j]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
cout << dp[n][m] << endl;
return 0;
}
- string 存字符串
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
const int N = 1005;
int dp[N][N];
int main() {
string a, b;
cin >> a >> b;
int n = a.size();
int m = b.size();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// string 原生0基，第i个字符对应索引 i-1
if (a[i-1] == b[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);//要么舍弃i 要么舍弃j
}
}
}
cout << dp[n][m] << endl;
return 0;
}
📌 真题演练
模型 4：编辑距离（进阶线性 DP）
问题描述
给定两个字符串，每次可以选择删除、插入、替换一个字符，求将第一个字符串转为第二个字符串的最少操作次数。
状态定义
dp[i][j]：将第一个字符串前 i 个字符转为第二个字符串前 j 个字符的最少操作数。
状态转移方程
若 str1[i-1] == str2[j-1]：dp[i][j] = dp[i-1][j-1]
否则：dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
在（删掉str1的第i个字符，在第i个后面增加1个字符和str2的第j个字符相等，替换第i个和第j个）
📌 真题演练
三、背包问题（线性 DP 重要分支）
背包问题是入门组 DP 核心考点，本质是“选与不选”的线性决策。
模型 1：01 背包（每件物品只能选 1 次）
问题描述
有 n 件物品，每件物品有重量 w[i] 和价值 v[i]，背包容量为 m，求最多能装下的最大总价值。
二维基础解法
状态定义：dp[i][j] 前 i 件物品，背包容量为 j 时的最大价值。
转移方程：
dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])
含义：两种选择——不选第 i 件（继承前 i-1 件结果）；选第 i 件（占用容量，加上价值）。
一维滚动数组优化（重点掌握）
核心技巧：逆序遍历容量，保证每件物品只被选一次。
模板代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1005;
int w[N], v[N], dp[N];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> w[i] >> v[i];
for (int i = 1; i <= n; i++) {
// 逆序遍历容量，01背包核心
for (int j = m; j >= w[i]; j--) {
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
cout << dp[m] << endl;
return 0;
}
📌 真题演练
模型 2：完全背包（每件物品可以选无限次）
问题描述
物品数量无限，其余条件同 01 背包。
核心区别
将 01 背包的逆序遍历容量改为顺序遍历容量，即可实现物品重复选取。
模板代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1005;
int w[N], v[N], dp[N];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> w[i] >> v[i];
for (int i = 1; i <= n; i++) {
// 顺序遍历容量，完全背包核心
for (int j = w[i]; j <= m; j++) {
dp[j] = (dp[j], dp[j - w[i]] + v[i]);
}
}
cout << dp[m] << endl;
return 0;
}
📌 真题演练
模型 3：多重背包（每件物品有固定数量）
问题描述
第 i 件物品最多有 c[i] 件，其余条件同 01 背包。
进阶解法：二进制优化
将数量 c 拆分为若干个 2 的幂次，转化为 01 背包求解。 多重背包二进制优化
📌 真题演练
- 模板题：洛谷 P 1776 宝物筛选 提交链接：https://www.luogu.com.cn/problem/P1776
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010, M = 2010;
int v[N], w[N]; // 原始物品体积、价值
int dp[M]; // dp数组：dp[j]表示容量j的背包最大价值
int n, V; // 物品种类数、背包总容量
int main()
{
cin >> n >> V;
int cnt = 0; // 拆分后的新物品总数
// 1. 二进制拆分所有物品
for(int i = 1; i <= n; i ++)
{
int vi, wi, si;
cin >> vi >> wi >> si;
// 二进制拆分
int k = 1;
while(si > 0)
{
int t = min(k, si); // 取出当前分组数量
cnt ++;
v[cnt] = t * vi;
w[cnt] = t * wi;
si -= t;
k *= 2;
}
}
// 2. 标准01背包DP
for(int i = 1; i <= cnt; i ++)
for(int j = V; j >= v[i]; j --)
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
cout << dp[V] << endl;
return 0;
}
四、区间 DP
1. 区间 DP 基础概念
定义
区间 DP 的状态以一段连续区间 [l, r] 作为划分依据，先求解长度更短的小区间，再合并推导更长的大区间。
适用场景：石子合并、括号匹配、字符串区间操作等。
三大核心特点
- 状态二维：
dp[l][r]代表区间l ~ r的最优解； - 遍历顺序：先枚举区间长度 len（从小到大），再枚举左端点 l，右端点
r = l + len - 1； - 分割点转移：大区间拆成两段小区间
[l, k]和[k+1, r]，枚举分割点 k 更新答案。
区间 DP 通用解题步骤
- 状态定义：
dp[l][r]区间 l 到 r 的最值/方案数； - 初始化：长度 len=1（单个元素）的区间，
dp[i][i]赋初始值； - 循环：外层区间长度 len 从 2~n；中层枚举左端点 l；计算 r=l+len-1；
- 枚举分割点 k ∈ [l, r-1]，状态转移；
- 答案为
dp[1][n]（整个大区间）。
2. 模型 1：石子合并（区间 DP 入门模板）
问题描述
一排 n 堆石子，每次合并相邻两堆，代价是两堆石子总数，求把所有石子合并成一堆的最小总代价。
预处理前缀和
sum[i]：前 i 堆石子总和，区间 [l, r] 合并代价增量 = sum[r] - sum[l-1]。
状态定义
dp[l][r]：合并第 l 堆到第 r 堆石子的最小总代价。
转移方程
dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r] + sum[r] - sum[l-1])
dp[l][k]：左半区间合并代价dp[k+1][r]：右半区间合并代价sum[r]-sum[l-1]：当前左右两段合并的一次性代价
边界初始化
所有长度为 1 的区间：dp[i][i] = 0，单堆石子无需合并，代价为 0。
完整模板代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 305;
const int INF = 0x3f3f3f3f;
int a[N], sum[N];
int dp[N][N];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum[i] = sum[i-1] + a[i];
}
// 初始化
memset(dp, 0x3f, sizeof(dp));
for (int i = 1; i <= n; i++) dp[i][i] = 0;
// len 区间长度，从2开始
for (int len = 2; len <= n; len++) {
// 左端点
for (int l = 1; l + len - 1 <= n; l++) {
int r = l + len - 1;
// 枚举分割点
for (int k = l; k < r; k++) {
dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r] + sum[r] - sum[l-1]);
}
}
}
cout << dp[1][n] << endl;
return 0;
}
3. 模型 2：括号匹配（最长合法括号序列）
问题描述
给定由 () 组成的字符串，求最长合法括号子序列长度。
状态定义
dp[l][r]：字符串 l~r 区间内最长合法括号长度。
转移规则
- 若
s[l]和s[r]配对()：dp[l][r] = dp[l+1][r-1] + 2 - 枚举分割点 k：
dp[l][r] = max(dp[l][r], dp[l][k] + dp[k+1][r])
核心代码片段
string s;
cin >> s;
int n = s.size();
for (int len = 2; len <= n; len++) {
for (int l = 0; l + len - 1 < n; l++) {
int r = l + len - 1;
if (s[l] == '(' && s[r] == ')') { //看首尾配对的情况 比如： （A）
dp[l][r] = dp[l+1][r-1] + 2;
}
for (int k = l; k < r; k++) {//分割是为了包含拼接的情况 比如（）（）
dp[l][r] = max(dp[l][r], dp[l][k] + dp[k+1][r]);
}
}
}
修改成求子串（要求连续）
// 求最长合法括号子串（必须连续）
for (int len = 2; len <= n; len++) {
for (int l = 0; l + len - 1 < n; l++) {
int r = l + len - 1;
// 只有当内部完全合法（长度等于 len-2）时，才能配对
if (s[l] == '(' && s[r] == ')' && dp[l+1][r-1] == len - 2) {
dp[l][r] = dp[l+1][r-1] + 2;
}
// 拼接依然需要，用于处理 "()()" 这种连续并列
for (int k = l; k < r; k++) {
dp[l][r] = max(dp[l][r], dp[l][k] + dp[k+1][r]);
}
}
}
4. 区间 DP 易错点总结
- 初始化无穷值：求最小值时 dp 数组初始化为 INF，求最大值初始化为 0；
- 遍历顺序不能颠倒：必须先短区间，后长区间；不能直接 l 从 1~n 循环；
- 分割点范围：k ∈ [l, r-1]，不能取到 r，否则右区间为空；
- 环形区间处理（石子合并环形）：数组复制一倍
a[n+i]=a[i]，区间长度不超过 n。
五、DP 解题通用步骤
- 读题抓核心：明确问题是求最大值、最小值还是方案数。
- 定义状态：用数组下标对应题目中的变量，清晰写出 dp 数组的含义。
- 推导转移：思考“最后一步怎么来的”，找到子问题到原问题的关系。
- 处理边界：确定初始值和数组下标范围，防止越界。
- 确定遍历顺序：
- 线性 DP：从小到大递推；
- 01 背包：容量逆序；完全背包：容量顺序；
- 区间 DP：先枚举区间长度，再枚举左右端点。
- 输出答案：根据状态定义，找到最终结果对应的 dp 数组位置。