【线性DP】问题模型总结
2025-10-28 16:12:43
发布于：上海
此贴仅供学习讨论，请勿非法传播
upd: 2025.5.11
- 增加了分组背包部分的题目对比。
0 动态规划的基本概念
0.1 基本思想
动态规划（Dynamic Programming），简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。
所以动态规划中每一个状态一定是由上一个状态推导出来的（如对第i个物品拿或者不拿），这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。
动态规划的入门思路：dfs暴力 -> 记忆化搜索 -> 递推DP。
0.2 解题步骤
-
① 根据题目所求确定DP数组含义。题目所求即为DP数组含义，所求相关即为DP数组的维度。
-
② 确定答案。根据题目含义和DP数组含义确定最终答案所在。
-
③ 确定状态转移方程。状态转移就是根据上一阶段的状态和决策来导出本阶段的状态，通常会根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
-
④ 初始化
-
⑤ 遍历顺序（确定目标）
-
⑥ 打印dp数组（用于debug）
0.3 动态规划特点
0.3.1 最优化原理（最优子结构）
如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
0.3.2 无后效性
即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
例如：计算状态f[2]后，结点a[3]的状态是不会变的，因此只需要加上结点a[3]就是状态f[3]。简单的说，就是在计算后面的数值时，只于当前的数值有关而与之前的数值无关。
0.3.3 子问题重叠
即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）
0.3.4 优化
DP的优化一般是对DP方程做等价变形。
1 单序列模型
1.1 基本概念
-
特点：状态通常只与序列的前一个或前几个状态有关。
-
DP数组定义：以第i位结尾的xx属性。
-
常见问题：
- 最长上升子序列（LIS） ：给定一个序列，找到最长的严格递增的子序列。
- 最大子数组和：在一个数组中找到一个连续子数组，使其和最大。
- 解码方法：给定一个数字字符串，计算解码方式的总数（如 'A' -> 1，'B' -> 2，...，'Z' -> 26）。
-
状态转移：通常
dp[i]表示以第i个元素结尾的子问题的解。
1.2 例题
1.2.1 最长上升子序列
问题描述
给定一个无序的整数数组，找到最长严格递增子序列的长度。
思路
- 状态定义：
dp[i]表示以nums[i]结尾的最长递增子序列长度 - 答案：
dp数组中的最大值 - 状态转移：对于每个
i，遍历j从0到i-1，如果nums[i] > nums[j]，则dp[i]可能等于dp[j]+1 - 初始化：每个位置的初始长度为1（至少包含自己）
- 遍历顺序：外层循环1到n，内层循环1到i
代码实现
for (int i = 1; i <= n; i++) {
dp[i] = 1;
for (int j = 1; j < i; j++) {
if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
ans = max(dp[i],ans);
}
cout << ans;
1.2.2 最长公共子序列
问题描述
给定两个字符串序列 X 和 Y，找出它们的最长公共子序列（LCS）的长度。子序列不要求连续，但必须保持相对顺序。
思路
-
初始化一个二维数组
dp，大小为(len(X)+1) x (len(Y)+1)，所有元素初始化为0。 -
遍历字符串X的每一个字符，对于每个字符，遍历字符串Y的每一个字符：
- 如果X的第i个字符和Y的第j个字符相等，则
dp[i][j] = dp[i-1][j-1] + 1。 - 否则，
dp[i][j]取dp[i-1][j]和dp[i][j-1]中的较大值。
- 如果X的第i个字符和Y的第j个字符相等，则
-
最终，
dp[len(X)][len(Y)]即为所求的最长公共子序列的长度。
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
char a[N], b[N];
int dp[N][N];
int main(){
cin >> a + 1;
cin >> b + 1;
memset(dp, 0, sizeof dp);
int al = strlen(a + 1);
int bl = strlen(b + 1);
for (int i = 1; i <= al; i++) {
for (int j = 1; j <= bl; 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[al][bl] << endl;
return 0;
}
2 双序列模型
2.1 基本概念
-
特点：涉及两个序列，状态通常与两个序列的前缀有关。
-
DP数组定义：以A序列的第i位结尾，以B序列的第j位结尾的xx属性。
-
常见问题：
- 最长公共子序列（LCS） ：给定两个序列，找到它们的最长公共子序列。
- 编辑距离：将一个字符串转换成另一个字符串所需的最少操作次数（插入、删除、替换）。
-
状态转移：通常
dp[i][j]表示第一个序列的前i个元素和第二个序列的前j个元素的解。
2.2 例题
2.2.1 最长公共子序列
问题描述
给定两个字符串 X 和 Y，要求找出它们的最长公共子序列的长度。子序列是指从原序列中删除一些元素（可以不连续）后剩下的序列，而不改变剩余元素的相对顺序。例如：
- X = "ABCBDAB"，Y = "BDCABA" 的一个 LCS 是 "BCBA"，长度为 4。
思路
最长公共子序列问题是一个经典的动态规划问题。以下是解决该问题的详细思路：
- 动态规划的定义
我们定义一个二维数组 dp[i][j]，表示字符串 X 的前 i 个字符和字符串 Y 的前 j 个字符的最长公共子序列的长度。
- 状态转移方程
- 如果
X[i-1] == Y[j-1]（即当前字符匹配），那么dp[i][j] = dp[i-1][j-1] + 1。 - 如果
X[i-1] != Y[j-1]（即当前字符不匹配），那么dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
- 初始化
dp[0][j] = 0和dp[i][0] = 0，因为空字符串与任何字符串的 LCS 长度为 0。
- 填充顺序
从 i=1 到 len(X)，j=1 到 len(Y)，依次填充 dp 表。
- 结果
dp[len(X)][len(Y)] 就是 X 和 Y 的最长公共子序列的长度。
示例演示
以 X = "ABCBDAB"，Y = "BDCABA" 为例：
-
初始化
dp表为 0。 -
逐步填充
dp表：- 当 X[0]='A' 和 Y[0]='B' 不匹配，
dp[1][1] = max(dp[0][1], dp[1][0]) = 0。 - 当 X[0]='A' 和 Y[3]='A' 匹配，
dp[1][4] = dp[0][3] + 1 = 1。 - 最终
dp[7][6] = 4。
- 当 X[0]='A' 和 Y[0]='B' 不匹配，
代码实现
//最长公共子序列
#include<bits/stdc++.h>
using namespace std;
string a, b;
int f[1005][1005];
int main(){
cin >> a >> b;
a = '0' + a;
b = '0' + b;
for (int i = 1; i < a.size(); i++) {
for (int j = 1; j < b.size(); j++) {
if (a[i] == b[j]) f[i][j] = f[i - 1][j - 1] + 1;
else f[i][j] = max(f[i - 1][j], f[i][j - 1]);
}
}
cout << f[a.size() - 1][b.size() - 1];
return 0;
}
2.2.2 编辑距离
问题描述
我们需要计算将字符串 A 转换成字符串 B 所需的最少操作次数。允许的操作有三种：
- 删除一个字符：从字符串 A 中删除一个字符。
- 插入一个字符：在字符串 A 中插入一个字符。
- 替换一个字符：将字符串 A 中的一个字符替换为另一个字符。
思路
这个问题是经典的编辑距离（Edit Distance） 问题，通常使用动态规划（Dynamic Programming, DP）来解决。
动态规划定义
定义 dp[i][j] 为将字符串 A 的前 i 个字符转换为字符串 B 的前 j 个字符所需的最少操作次数。
初始化
dp[0][j] = j：将空字符串 A 转换为 B 的前j个字符，需要进行j次插入操作。dp[i][0] = i：将 A 的前i个字符转换为空字符串 B，需要进行i次删除操作。
状态转移方程
对于 dp[i][j]，我们考虑以下情况：
-
A[i-1] == B[j-1] ：当前字符相同，不需要操作，
dp[i][j] = dp[i-1][j-1]。 -
A[i-1] != B[j-1] ：需要进行以下三种操作之一，取最小值：
- 插入：
dp[i][j-1] + 1（在 A 的前i个字符后插入 B[j-1]） - 删除：
dp[i-1][j] + 1（删除 A[i-1]） - 替换：
dp[i-1][j-1] + 1（将 A[i-1] 替换为 B[j-1]）
- 插入：
因此，状态转移方程为：
if A[i-1] == B[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1
示例计算
让我们用示例 A = "sfdqxbw", B = "gfdgw" 来计算：
初始化：
- A 的长度 m = 7, B 的长度 n = 5。
dp[0][j] = j,dp[i][0] = i。
逐步填充 dp 表：
（这里只展示关键步骤）
dp[1][1]: A[0]='s', B[0]='g' → 替换，dp[1][1] = dp[0][0] + 1 = 1dp[1][2]: A[0]='s', B[1]='f' → 插入 'f'，dp[1][2] = dp[1][1] + 1 = 2dp[2][1]: A[1]='f', B[0]='g' → 删除 'f'，dp[2][1] = dp[1][1] + 1 = 2dp[2][2]: A[1]='f', B[1]='f' → 相同，dp[2][2] = dp[1][1] = 1- 继续填充直到
dp[7][5]。
最终 dp[7][5] 就是答案。
代码实现
//编辑距离
#include<iostream>
#include<algorithm>
using namespace std;
int dp[2010][2010],n,m;
string a,b;
int main(){
cin>>a>>b;
n=a.size();
m=b.size();
a=' '+a;
b=' '+b;
for(int i=0;i<=n;i++){
dp[i][0]=i;
}
for(int i=0;i<=m;i++){
dp[0][i]=i;
}
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];
else dp[i][j]=min({dp[i-1][j],dp[i-1][j-1],dp[i][j-1]})+1;
}
}cout<<dp[n][m];
return 0;
}
3 计数问题
3.1 基本概念
特点：要求统计满足条件的方案数，需注意避免重复计数。
3.2 例题
3.2.1 神奇的魔法币
有若干种魔法币，每种魔法币有固定面值，可以无限使用。支付魔法币时，必须恰好等于愿望的总价值才能实现愿望。求支付的方案数量。
3.2.2 思路
这个问题类似于经典的“完全背包问题”或“硬币找零问题”，其中我们需要计算用无限数量的不同面值的硬币凑出某个金额的总方法数。
对于每一种硬币面值 coin，我们更新 dp 数组：
对于每个金额 i 从 coin 到 m，dp[i] += dp[i - coin]。
这表示：如果我们要凑出金额 i，可以考虑使用一个面值为 coin 的硬币，然后剩下的金额 i - coin 的凑法数就是 dp[i - coin]。因此，dp[i] 增加 dp[i - coin]。
3.2.3 代码实现
//完全背包问题
#include <bits/stdc++.h>
using namespace std;
long long m, n, dp[110][3010], a[110];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 0; i <= n; i++)
dp[i][0] = 1;
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= m; ++j) {
if (j >= a[i])
dp[i][j] = dp[i - 1][j] + dp[i][j - a[i]];
else
dp[i][j] = dp[i - 1][j];
}
cout << dp[n][m];
return 0;
}
4 背包问题
4.1 基本概念
特点：在容量限制下选择物品，状态包含“容量”维度。
4.2 01背包
问题描述
有n个物品，背包容量为m，第i件物品的费用是cost[i]，价值是value[i]。
**每一个物品只能拿一次。**
求拿哪些物品放入背包能使得价值最大。
思路
每种只有一件，可以选择放或者不放。
状态转移方程
每一次从i,j的正上方和左上方转移过来。
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
不放：dp[i][j] = dp[i-1][j]
从上一个物品的同一个容量的最大价值继承过来
放：dp[i][j] = dp[i-1][j-c[i]] + v[i];
if(j >= c[i]) dp[i][j] = max(dp[i-1][j],dp[i-1][j-c[i]] + v[i]);
else dp[i][j] = dp[i-1][j];
}
}
滚动数组优化
for(int i = 1; i <= n; i++){
for(int j = c; j >= w[i]; j--){
//数据从i,j的正上方和左上方更新
//为了让每一个j在第i行时能用第i-1行的数据，所以采用逆序更新
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
4.3 完全背包
问题描述
有n个物品，背包容量为m，第i件物品的费用是cost[i]，价值是value[i]。
<span data-type="text" style="color: var(--b3-font-color8);">每一个物品可以无数次。</span>
求拿哪些物品放入背包能使得价值最大。
思路
借鉴01背包的思路，每次物品可以放或者不放。
状态转移方程
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
if(j >= c[i]) dp[i][j] = max(dp[i-1][j],dp[i][j-c[i]]+v[i]);
else dp[i][j] = dp[i-1][j];
}
}
滚动数组优化
for(int i=1;i<=n;i++){
for(int j = w[i]; j <= m; j++){
//数据从i,j的正上方和左上方更新
//为了让每一个j在第i行时能用第i-1行的数据，所以采用逆序更新
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
4.4 多重背包
问题描述
有n个物品，背包容量为m，第i件物品的费用是cost[i]，价值是value[i]。
**每个物品可以拿有限多个**。
求拿哪些物品放入背包能使得价值最大。
思路
将可以拿s[i]次的物品，视作有s[i]个。
状态转移方程
for(int i=1;i<=n;i++){
cin>>x>>y>>z;//物品的体积、价值、数量
for(int j=1;j<=z;j++){
c[++cnt]=x;
w[cnt]=y;
}
}
for(int i=1;i<=cnt;i++){
for(int j=v;j>=c[i];j--){
dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
}
}
二进制优化
struct Good{
long long v, w;
}goods[505];
int cnt;
for (int i = 1; i <= n; i++){
int v, w, s;
cin >> v >> w >> s;
for (int k = 1; k <= s; k *= 2) {
s -= k;
goods[++cnt] = {k*v,k*w};
}
if(s > 0) goods[++cnt] = {s*v,s*w};
}
for (int it=1;it<=cnt;it++){
for (int j = m; j >= goods[it].v; j--) {
f[j] = max(f[j], f[j - goods[it].v] + goods[it].w);
}
}
4.5 混合背包
问题描述
有n个物品，背包容量为m，第i件物品的费用是cost[i]，价值是value[i]。
<span data-type="text" style="color: var(--b3-font-color8);">每一个物品可以拿p[i]次，0<=p[i]<=x。</span>
p[i] = 0，可以取无限次。
p[i] > 0，可以取p[i]次
求拿哪些物品放入背包能使得价值最大。
思路
当p[i] = 0的时候，转化为完全背包。
当p[i] = 1的时候，转化为01背包。
当p[i] > 1的时候，转化为多重背包。
状态转移方程
for(int i=1;i<=n;i++){
if(p[i] == 0){
//完全背包
}
else{
//多重背包
for(int k=1;k<=p[i];k++){
for(int j=c[i];j<=m;j++){
dp[j] = max(dp[j],[j-c[i]]+v[i]);
}
}
}
}
二进制优化
拆成1，2，4，8，...，和剩下的。合并一个新的物品
for(int i=1;i<=n;i++){
int k = 1;//当前的物品有多少个
while(k <= p[i]){
int cost = c[i] * k;
int value = v[i] * k;
if(cost > m) break;
//视作01背包处理
for(int j=cost;j<=m;j++){
dp[j] = max(dp[j],dp[j-cost]+value);
}
p[i] -= k;
k *= 2;
}
if(p[i] > 0){
int cost = c[i] * p[i];
int value = v[i] * p[i];
if(cost > m) continue;
//视作01背包处理
for(int j=cost;j<=m;j++){
dp[j] = max(dp[j],dp[j-cost]+value);
}
}
}
4.6 分组背包
4.6.1 问题描述
有n个物品，有T个组，每个物品都属于不同的组。背包容量为m，第i件物品的费用是cost[i]，价值是value[i]，第i个物品属于t[i]组。
**每组只能拿一个物品。**
求拿哪些物品放入背包能使得价值最大。
4.6.2 思路
先将不同的物品分类。
对每一组物品，用01背包的方式求能拿的最大价值。
4.6.3 状态转移方程（朴素版）
#include<iostream>
using namespace std;
int main(){
//1、将数据输入到二维vector里
vector<node> ve[15];
for (int i = 0; i < N; i++) {
int W, C, P;
cin >> W >> C >> P;
ve[P].push_back({ W,C });
}
//2、遍历顺序
int dp[15][205]//第i组，容量为j的最大xxx
for(int i=1;i<=T;i++){
for(int j=0;j<=V;j++){
//k要遍历某一组物品的数量,ve[i]
//ve[i].size():保存的是第i个v的数据个数
dp[i][j] = dp[i-1][j];//不拿物品
for(int k=0;k<ve[i].size();k++){
if(j >= ve[i][k].w)
//拿物品
dp[i][j] = max(dp[i][j],dp[i-1][j-ve[i][k].w]+ve[i][k].v);
}
}
}
//3、答案
cout << dp[T][V];
return 0;
}
/*
对每组物品做一个01背包
需求1：快速的遍历到每一组的物品
需要将物品按组号分类 ——二维的vector
vector<int> v;
vector<int> v2[100];
v2[0],v2[1],v2[2] 。。。 v2[99]
v2[0].push_back(1); v2[0][0]
v2[0][0] = 1;
需求2：需要遍历每一个物品的两个属性
需要用结构体vector
struct node{
int w,c;重量，价值
};
vector<node> v[100];
v[0].push_back({1,10});
*/
4.6.4 滚动数组优化
#include<bits/stdc++.h>
using namespace std;
struct Node{
int w,c;
};
vector<Node> ve[150000];
int dp[2005];
int main(){
int v,n,t;
cin>>v>>n>>t;
for(int i=1;i<=n;i++){
int ww,cc,pp;
cin>>ww>>cc>>pp;
ve[pp].push_back({ww,cc});
}
for(int i=1;i<=t;i++){
for(int j=v;j>=0;j--){
for(int k=0;k<ve[i].size();k++){
if(ve[i][k].w<=j)dp[j]=max(dp[j],dp[j-ve[i][k].w]+ve[i][k].c);
}
}
}
cout<<dp[v];
return 0;
}
4.6.5 例题
4.6.5.1 T46887.通天之分组背包
问题描述
- 有一个容量为
m的背包。 - 有
n个物品，每个物品有自己的重量a_i、价值b_i和所属的组别c_i。 - 这些物品被分成了
k组（组别编号从 1 到k）。 - 每组中的物品是相互冲突的，这意味着在同一组中，你最多只能选择其中一个物品（或者不选）。
- 目标是选择一些物品放入背包，使得总重量不超过
m，且总价值最大。
思路
-
状态定义：定义
dp[j]表示背包容量为j时能获得的最大价值。 -
组处理：对于每一组，我们考虑选择组内的哪一个物品（或不选）能最大化
dp[j]。- 对于每个容量
j，遍历组内的所有物品，检查是否可以将该物品放入背包（即j >= a_i），并更新dp[j]。
- 对于每个容量
-
顺序：通常先遍历组，然后遍历背包容量（从大到小，类似于 01 背包），最后遍历组内的物品。
代码实现
#include<bits/stdc++.h>
using namespace std;
struct node {
int w, c;
};
long long dp[1009];
vector<node> ve[109];
int main() {
int m, n;
cin >> m >> n;
for (int i = 0; i < n; i++) {
int a, b, c;
cin >> a >> b >> c;
ve[c].push_back({ a,b });
}
for (int i = 1; i <= 100; i++) {
for (int j = m; j >= 0; j--) {
for (int k = 0; k < ve[i].size(); k++) {
if (j >= ve[i][k].w) dp[j] = max(dp[j], dp[j - ve[i][k].w] + ve[i][k].c);
}
}
}
cout << dp[m];
return 0;
}
有帮助，赞一个