原文链接：https://woozie.blog/index.php/2022/10/09/26/
目录
背包
01背包（每个物品只有一个）
朴素01背包
dp[i][j]的含义：前i个物品，容量为j的情况下能装物品的价值最大值
第一层循环——从1到n个物品
第二层循环——从容量0到m
对于第i个物品，当容量为j时
1. v[i]>j 即物品大于容量，不能放，则继承 dp[i][j]=dp[i-1][j];
2. v[i]<=j 选择最大价值 max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]) //dp[i-1][j]为不放直接继承，dp[i-1][j-v[i]]+w[i]为放第i件物品
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m; //n物品个数，m背包容量
int v[N],w[N]; //v物品所占空间，w物品价值
int dp[N][N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d%d",&v[i],&w[i]);
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
if(j<v[i])
dp[i][j]=dp[i-1][j]; //继承
else
dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]); //更新
printf("%d",dp[n][m]);
}01背包一维数组优化
dp[i][j]能求得任意i，j情况下的最优解，但由于最终只需要求dp[n][m]，所以只需要一维就可以维持
枚举背包容量需要逆序！
简单来说因为正序会使后面要用到的数据被覆盖，而倒序不会出现这个问题。
具体来讲我也忘了
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int dp[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d%d",&v[i],&w[i]);
for(int i=1;i<=n;i++)
for(int j=m;j>=v[i];j--)
dp[j]=max(dp[j],dp[j-v[i]]+w[i]); //倒序，防止覆盖
printf("%d",dp[m]);
}完全背包（物品无限）
朴素完全背包
第一层循环——枚举物品
第二层循环——枚举容量
第三层循环——枚举个数 条件为k*v[i]<=j，超过容量即退出
递推式 dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]) 前者表示维持当前最大值，后者表示取k个i物品
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int dp[N][N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d%d",&v[i],&w[i]);
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
for(int k=0;k*v[i]<=j;k++)
dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]);
printf("%d",dp[n][m]);
}完全背包优化
优化思路
f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2*v]+2*w , f[i-1,j-3*v]+3*w , .....)
f[i , j-v]= max( f[i-1,j-v] , f[i-1,j-2*v] + w , f[i-1,j-3*v]+2*w , .....)
由上两式，可得出如下递推关系：
f[i][j]=max(f[i,j-v]+w , f[i-1][j]) #include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int dp[N][N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d%d",&v[i],&w[i]);
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++) //从小到大枚举，与01背包不同
{
dp[i][j]=dp[i-1][j];
if(j>=v[i])
dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);
}
}
printf("%d",dp[n][m]);
}完全背包一维优化
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int dp[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d%d",&v[i],&w[i]);
for(int i=1;i<=n;i++)
for(int j=v[i];j<=m;j++)
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
printf("%d",dp[m]);
}多重背包（物品有限）
01背包是特殊的多重背包
代码与01背包雷同
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,m;
int v[N],w[N],s[N];
int dp[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d%d%d",&v[i],&w[i],&s[i]);
for(int i=1;i<=n;i++)
for(int j=m;j>=v[i];j--)
for(int k=0;k<=s[i]&&k*v[i]<=j;k++) //01背包的k相当于恒为1
dp[j]=max(dp[j-k*v[i]]+k*w[i],dp[j]);
printf("%d",dp[m]);
}区间dp
求区间最优解，将区间分隔为更小的区间，再由小区间最优解得到大区间最优解
模板
for(int len=1;len<=n;len++) //先枚举长度
{
for(int i=1;i+len-1<=n;i++) //枚举起点
{
int j=i+len-1; //由起点和长度得出终点
for(int k=i;k+1<=j;k++)
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+______);
}
} 线性
石子合并
#include<bits/stdc++.h>
using namespace std;
const int N=310;
int a[N],b[N],dp[N][N];
int n;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[i]=b[i-1]+a[i];//记录前缀和
}
memset(dp,0x3f3f3f3f,sizeof(dp));//初始化
for(int len=1;len<=n;len++)
{
for(int i=1;i+len-1<=n;i++)
{
int j=len+i-1;
if(len==1)
{
dp[i][j]=0;//最小区间
continue;
}
for(int k=i;k<=j-1;k++)
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+b[j]-b[i-1]);
}
}
printf("%d",dp[1][n]);
}环状
思路：将链打开
只需要将前n-1个数复制到后面
如123456 -> 12345612345
最后求max(dp(1,n),dp(2,n+1),......,dp(n,2n-1))
题目：环形石子合并
#include<bits/stdc++.h>
using namespace std;
const int N=210;
int n;
int dpmax[2*N][2*N],dpmin[2*N][2*N],a[2*N];
int b[2*N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
a[i+n]=a[i];
}
for(int i=1;i<=2*n;i++)
b[i]=b[i-1]+a[i];
memset(dpmin,0x3f3f3f,sizeof(dpmin));
memset(dpmax,0,sizeof(dpmax)); //注意预处理！！！！
for(int len=1;len<=n;len++)
{
for(int i=1;i+len-1<=2*n;i++)
{
int j=i+len-1;
if(len==1)
{
dpmax[i][i]=0;
dpmin[i][i]=0;
continue;
}
for(int k=i;k+1<=j;k++)
{
dpmin[i][j]=min(dpmin[i][j],dpmin[i][k]+dpmin[k+1][j]+b[j]-b[i-1]);
dpmax[i][j]=max(dpmax[i][j],dpmax[i][k]+dpmax[k+1][j]+b[j]-b[i-1]);
}
}
}
int maxn=0,minn=0x3f3f3f;
for(int i=1;i<=n;i++)
maxn=max(dpmax[i][i+n-1],maxn),minn=min(dpmin[i][i+n-1],minn);
printf("%d\n%d",minn,maxn);
}
计数dp
AcWing 900. 整数划分
题意：一个正整数 n 可以表示成若干个正整数之和，形如：n=n1+n2+…+nk，其中 n1≥n2≥…≥nk,k≥1。有多少种表示方法。
可转化为完全背包
有容量为1~n的n种物品，使背包容量恰好为n，问有多少种放法
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
const int MOD=1e9+7;
int n;
int dp[N];
int main()
{
scanf("%d",&n);
dp[0]=1; //0有一种放法，后面的状态全由0转移出来
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
{
dp[j]+=dp[j-i];
dp[j]%=MOD;
}
printf("%d",dp[n]);
}Acwing 1021. 货币系统
给你一个n种面值的货币系统，求组成面值为m的货币有多少种方案。
输入格式
第一行，包含两个整数n和m。
接下来n行，每行包含一个整数，表示一种货币的面值。
输出格式
共一行，包含一个整数，表示方案数。
数据范围
n≤15,m≤3000
输入样例：
3 10
1
2
5
输出样例：
10#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=20;
const int M=3010;
ll n,m;
ll dp[M],a[N];
int main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
dp[0]=1;
for(int i=1;i<=n;i++)
for(int j=a[i];j<=m;j++)
dp[j]+=dp[j-a[i]];
printf("%lld",dp[m]);
}线性dp
最长上升子序列
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n;
int a[N],dp[N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
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);
}
int res=0;
for(int i=1;i<=n;i++)
res=max(res,dp[i]);
printf("%d",res);
}最短编辑距离
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
string a,b;
int dp[N][N];
int main()
{
scanf("%d",&n);
cin>>a;
scanf("%d",&m);
cin>>b;
memset(dp,0x3f3f3f3f,sizeof(dp)); //求最小值要初始化！！！！
for(int i=1;i<=n;i++) //初始化
dp[i][0]=i;
for(int i=0;i<=m;i++) //初始化
dp[0][i]=i;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
int x=i+1,y=j+1;
dp[x][y]=min(dp[x-1][y-1],min(dp[x-1][y],dp[x][y-1]))+1;
if(a[i]==b[j])
dp[x][y]=min(dp[x][y],dp[x-1][y-1]);
}
printf("%d",dp[n][m]);
}
本文含有隐藏内容，请 开通VIP 后查看