线性dp 8.29(附赠背包模板)
2026-08-30 13:33:29
发布于：上海
解题步骤：
1、状态：描述【子问题】所需要的最少信息，一般来说，问题问什么，dp状态就是什么。
例：
(1)最长上升子序列：dp[i]表示第i项的最长上升子序列的值。
(2)编辑距离：dp[i][j]表示A数组的前i个字符变成B数组的前j个字符所需的最小操作次数。
确定状态的步骤：
(1)先确定题目在问什么 -> dp数组最终要存储什么。
(2)再确定存储的内容跟什么有关，是哪些要素在影响这个？ -> 这些要素就是下标。
(3)这些下标组合起来，就是状态 -> “从前i个中选，使和恰好为j的方案数”。
2、答案：好的状态设计能够快速确定答案的位置。
例：
(1)dp[n]表示第n项斐波那契数列的值。
(2)dp[n][m]表示A前n个字符转化成B的前m个字符所需的最小操作次数。
3、状态转移方程：决策如何到达第i项
通用的做法：用表格列出某个样例的dp数组的所有值，寻找其中特殊的变化规律，用代码描述它。
例：
(1)最大值/最小值：max/min，最小值一般需要初始化。
(2)方案数：一般需要各项累加起来。
4、初始化：给不满足转移方程的特殊边界值，单独赋值。
例：
(1)斐波那契数列的第一项和第二项：dp[1]=1,dp[2]=1;
5、遍历顺序：
(1)01背包：内层循环逆序。完全背包：内层循环正序。
6、调试：把dp数组打印出来，手算小样例的数据是否匹配，不要只用眼睛逐行看代码。
例：
U145095.[USACO04NOV] Apple Catching G
题目描述
很少有人知道奶牛爱吃苹果。农夫约翰的农场上有两棵苹果树（编号为 1 和 2），每一棵树上都长满了苹果。
奶牛贝茜无法摘下树上的苹果，所以她只能等待苹果从树上落下。但是，由于苹果掉到地上会摔烂，
贝茜必须在半空中接住苹果（没有人爱吃摔烂的苹果）。贝茜吃东西很快，她接到苹果后仅用几秒钟就能吃完。
每一分钟，两棵苹果树其中的一棵会掉落一个苹果。贝茜已经过了足够的训练，只要站在树下就一定能接住这棵树上掉落的苹果。
同时，贝茜能够在两棵树之间快速移动（移动时间远少于1 分钟），因此当苹果掉落时，她必定站在两棵树其中的一棵下面。
此外，奶牛不愿意不停地往返于两棵树之间，因此会错过一些苹果。
苹果每分钟掉落一个，共 T 分钟，贝茜最多愿意移动 W 次。
现给出每分钟掉落苹果的树的编号，要求判定贝茜能够接住的最多苹果数。开始时贝茜在 1 号树下。
输入格式
第一行 2 个数，T 和 W。
接下来的 T 行，每行一个数，代表在该分钟苹果是从 1 号苹果树还是从 2 号苹果树上掉下来的。
输出格式
输出一行，一个数，为奶牛最多接到的苹果的数量。
简要说明：求能接住最多的苹果数。(dp就是个枚举，分析题目问题有关的变量，枚举相关变量)
思路：能接住最多的苹果数与移动次数，掉落时间有关。所以要知道第T分钟，一共移动了多少次。所以用dp[i][j]表示第i分钟，移动了j次所获得的最大苹果数。
即：每分钟动/不动。
#include<bits/stdc++.h>
using namespace std;
int a[1005];
int f[1005][35];
int main(){
int n,m;
cin >> n >> m;
for(int i=1;i<=n;i++){
cin >> a[i];
}
memset(f,-1,sizeof(f));
f[0][0]=0;
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
int now=1+j%2;
int get=(a[i]==now)?1:0;
if(j>=1&&f[i-1][j-1]>=0){
f[i][j]=max(f[i][j],f[i-1][j-1]+get);
}
if(f[i-1][j]>=0){
f[i][j]=max(f[i-1][j]+get,f[i][j]);
}
}
}
int ans=0;
for(int i=0;i<=m;i++){
if(f[n][i]>ans){
ans=f[n][i];
}
}
cout << ans;
return 0;
}
附赠：
1、01背包模板：
U143290.[NOIP 2005 普及组] 采药
#include<bits/stdc++.h>
using namespace std;
int t, m;
int w[105], v[105];
int dp[1005];
int main(){
cin >> t >> m;
for(int i=1;i<=m;i++){
cin >> w[i] >> v[i];
}
for(int i=1;i<=m;i++){
for(int j=t;j>=0;j--){
if(j>=w[i]){
dp[j]=max(dp[j-w[i]]+v[i],dp[j]);
}
}
}
cout << dp[t];
return 0;
}
2、完全背包模板：
A21096.疯狂的采药
#include<bits/stdc++.h>
using namespace std;
int m,n;
int w[100002],c[100002];
int dp[100002];
int main(){
cin >> m >> n;
for(int i=1;i<=n;i++){
cin >> w[i] >> c[i];
}
for(int i=1;i<=n;i++){
for(int j=w[i];j<=m;j++){
dp[j]=max(dp[j],c[i]+dp[j-w[i]]);
}
}
cout << dp[m];
}
这里空空如也
有帮助，赞一个