动态规划dp_dp[i][j]=dp[i-1][j] || dp[i-1][abs(j-w[i])] ||dp[i

原文链接：https://woozie.blog/index.php/2022/10/09/26/

目录

背包

01背包（每个物品只有一个）

朴素01背包

01背包一维数组优化

完全背包（物品无限）

朴素完全背包

完全背包优化

完全背包一维优化

多重背包（物品有限）

区间dp

线性

环状

计数dp

线性dp

 

---

 

背包

 

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]);
}