DP与背包
当前没有测试数据。
动态规划csp原题（2024） 动态规划csp原题（2023-1） 动态规划csp原题（2023-2） 动态规划csp原题（2022）
一、动态规划基础概念
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]);
}
}
}
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] = max(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
四、DP 解题通用步骤
- 读题抓核心：明确问题是求最大值、最小值还是方案数。
- 定义状态：用数组下标对应题目中的变量，清晰写出 dp 数组的含义。
- 推导转移：思考“最后一步怎么来的”，找到子问题到原问题的关系。
- 处理边界：确定初始值和数组下标范围，防止越界。
- 确定遍历顺序：线性 DP 通常从小到大；背包注意 01 逆序、完全顺序。
- 输出答案：根据状态定义，找到最终结果对应的 dp 数组位置。