dp类总结

1.传统背包问题以及变形

1）01背包问题：

     例题

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+6;
const int inf=0x3f3f3f3f3f3f3f3f;
int v[N],w[N],dp[N];
void solve()
{
	int n,V;cin>>n>>V;
	for(int i=1;i<=n;i++)
	{
		cin>>v[i]>>w[i]; 
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=V;j>=v[i];j--)
		{
			dp[j]=max(dp[j-v[i]]+w[i],dp[j]);
		}
	}
	cout<<dp[V];
}
signed main()
{
	//ios_base::sync_with_stdio(false);
	//cin.tie(nullptr),cout.tie(nullptr);
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

2）完全背包问题：

     例题

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+6;
const int inf=0x3f3f3f3f3f3f3f3f;
int v[N],w[N],dp[N];
void solve()
{
	int n,V;cin>>n>>V;
	for(int i=1;i<=n;i++)
	{
		cin>>v[i]>>w[i]; 
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=v[i];j<=V;j++)
		{
			dp[j]=max(dp[j-v[i]]+w[i],dp[j]);
		}
	}
	cout<<dp[V];
}
signed main()
{
	//ios_base::sync_with_stdio(false);
	//cin.tie(nullptr),cout.tie(nullptr);
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

3）多重背包问题：

      例题

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+6;
const int inf=0x3f3f3f3f3f3f3f3f;
int v[N],w[N],dp[N];
void solve()
{
	int n,V;cin>>n>>V;int nct=0;
	for(int i=1;i<=n;i++)
	{
		int p,q,r;cin>>p>>q>>r;
		int k=1;
		while(k<r)
		{
			v[++nct]=p*k,w[nct]=q*k;
			r-=k;
			k*=2;
		}
		if(r)
		{
			v[++nct]=p*r;w[nct]=q*r;
		}
	}
	for(int i=1;i<=nct;i++)
	{
		for(int j=V;j>=v[i];j--)
		{
			dp[j]=max(dp[j-v[i]]+w[i],dp[j]);
		}
	}
	cout<<dp[V];
}
signed main()
{
	//ios_base::sync_with_stdio(false);
	//cin.tie(nullptr),cout.tie(nullptr);
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

4）分组背包问题：

      例题

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e3+6;
const int inf=0x3f3f3f3f3f3f3f3f;
int v[N][N],w[N][N],dp[N],s[N];
void solve()
{
	int n,V;cin>>n>>V;
	for(int i=1;i<=n;i++)
	{
		cin>>s[i];
		for(int j=1;j<=s[i];j++)
		{
			cin>>v[i][j]>>w[i][j];
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=V;j>=0;j--)
		{
			for(int k=1;k<=s[i];k++)
			{
				if(j>=v[i][k])
				{
					dp[j]=max(dp[j],dp[j-v[i][k]]+w[i][k]);
				}
			}
		}
	}
	cout<<dp[V];
}
signed main()
{
	//ios_base::sync_with_stdio(false);
	//cin.tie(nullptr),cout.tie(nullptr);
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

5）01背包求体积恰好等于V

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e3+6;
const int inf=0x3f3f3f3f3f3f3f3f;
int dp[N];
void solve()
{
	int n,V;cin>>n>>V;
	dp[0]=1;
	for(int i=1;i<=n;i++)
	{
		int v;cin>>v;
		for(int j=V;j>=v;j--)
		{
			dp[j]+=dp[j-v];
		}
	}
	cout<<dp[V];
}
signed main()
{
	//ios_base::sync_with_stdio(false);
	//cin.tie(nullptr),cout.tie(nullptr);
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

6)完全背包求体积恰好等于V

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e3+6;
const int inf=0x3f3f3f3f3f3f3f3f;
int dp[N];
void solve()
{
	int n,V;cin>>n>>V;
	dp[0]=1;
	for(int i=1;i<=n;i++)
	{
		int v;cin>>v;
		for(int j=v;j<=V;j++)
		{
			dp[j]+=dp[j-v];
		}
	}
	cout<<dp[V];
}
signed main()
{
	//ios_base::sync_with_stdio(false);
	//cin.tie(nullptr),cout.tie(nullptr);
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

7）01背包求体积不超过V

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e3+6;
const int inf=0x3f3f3f3f3f3f3f3f;
int dp[N];
void solve()
{
	int n,V;cin>>n>>V;
	fill(dp,dp+V+1,1);
	for(int i=1;i<=n;i++)
	{
		int v;cin>>v;
		for(int j=V;j>=v;j--)
		{
			dp[j]+=dp[j-v];
		}
	}
	cout<<dp[V];
}
signed main()
{
	//ios_base::sync_with_stdio(false);
	//cin.tie(nullptr),cout.tie(nullptr);
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

8）完全背包求体积不超过V

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e3+6;
const int inf=0x3f3f3f3f3f3f3f3f;
int dp[N];
void solve()
{
	int n,V;cin>>n>>V;
	fill(dp,dp+V+1,1);
	for(int i=1;i<=n;i++)
	{
		int v;cin>>v;
		for(int j=v;j<=V;j++)
		{
			dp[j]+=dp[j-v];
		}
	}
	cout<<dp[V];
}
signed main()
{
	//ios_base::sync_with_stdio(false);
	//cin.tie(nullptr),cout.tie(nullptr);
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

 9)01背包求体积至少是V 

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e3+6;
const int inf=0x3f3f3f3f3f3f3f3f;
int dp[N];
void solve()
{
	int n,V;cin>>n>>V;
	dp[0]=1;
	for(int i=1;i<=n;i++)
	{
		int v;cin>>v;
		for(int j=V;j>=0;j--)
		{
			dp[j]+=dp[max(0ll,(j-v))];
		}
	}
	cout<<dp[V];
}
signed main()
{
	//ios_base::sync_with_stdio(false);
	//cin.tie(nullptr),cout.tie(nullptr);
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

10）01背包求体积恰好为V的最大价值

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e3+6;
const int inf=0x3f3f3f3f3f3f3f3f;
int dp[N];
void solve()
{
	int n,V;cin>>n>>V;
	memset(dp,-inf,sizeof dp);
	dp[0]=0;
	for(int i=1;i<=n;i++)
	{
		int v,w;cin>>v>>w;
		for(int j=V;j>=v;j--)
		{
			dp[j]=max(dp[j],dp[j-v]+w);
		}
	}
	cout<<dp[V];
}
signed main()
{
	//ios_base::sync_with_stdio(false);
	//cin.tie(nullptr),cout.tie(nullptr);
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

11）01背包求体积恰好为V的最小价值

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e3+6;
const int inf=0x3f3f3f3f3f3f3f3f;
int dp[N];
void solve()
{
	int n,V;cin>>n>>V;
	memset(dp,inf,sizeof dp);
	dp[0]=0;
	for(int i=1;i<=n;i++)
	{
		int v,w;cin>>v>>w;
		for(int j=V;j>=v;j--)
		{
			dp[j]=min(dp[j],dp[j-v]+w);
		}
	}
	cout<<dp[V];
}
signed main()
{
	//ios_base::sync_with_stdio(false);
	//cin.tie(nullptr),cout.tie(nullptr);
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

12）完全背包求体积恰好为V的最大价值

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e3+6;
const int inf=0x3f3f3f3f3f3f3f3f;
int dp[N];
void solve()
{
	int n,V;cin>>n>>V;
	memset(dp,-inf,sizeof dp);
	dp[0]=0;
	for(int i=1;i<=n;i++)
	{
		int v,w;cin>>v>>w;
		for(int j=v;j<=V;j++)
		{
			dp[j]=max(dp[j],dp[j-v]+w);
		}
	}
	cout<<dp[V];
}
signed main()
{
	//ios_base::sync_with_stdio(false);
	//cin.tie(nullptr),cout.tie(nullptr);
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

13）完全背包求体积恰好为V的最小价值

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e3+6;
const int inf=0x3f3f3f3f3f3f3f3f;
int dp[N];
void solve()
{
	int n,V;cin>>n>>V;
	memset(dp,inf,sizeof dp);
	dp[0]=0;
	for(int i=1;i<=n;i++)
	{
		int v,w;cin>>v>>w;
		for(int j=v;j<=V;j++)
		{
			dp[j]=min(dp[j],dp[j-v]+w);
		}
	}
	cout<<dp[V];
}
signed main()
{
	//ios_base::sync_with_stdio(false);
	//cin.tie(nullptr),cout.tie(nullptr);
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

14）完全背包求总体积至少是V的最小价值

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e3+6;
const int inf=0x3f3f3f3f3f3f3f3f;
int dp[N];
void solve()
{
	int n,V;cin>>n>>V;
	memset(dp,inf,sizeof dp);
	dp[0]=0;
	for(int i=1;i<=n;i++)
	{
		int v,w;cin>>v>>w;
		for(int j=V;j>=0;j--)
		{
			dp[j]=min(dp[j],dp[max(0ll,j-v)]+w);
		}
	}
	cout<<dp[V];
}
signed main()
{
	//ios_base::sync_with_stdio(false);
	//cin.tie(nullptr),cout.tie(nullptr);
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

2.整数划分

1）整数n划分成k个数之和的方案数

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+6;
const int inf=0x3f3f3f3f3f3f3f3f;
int dp[1100][1100];
void solve()
{
	dp[0][0]=1;
	int n,k;cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			dp[i][j]=dp[i-1][j-1]+dp[i-j][j];
		}
	}
	cout<<dp[n][k];
}
signed main()
{
	//ios_base::sync_with_stdio(false);
	//cin.tie(nullptr),cout.tie(nullptr);
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

2)  整数n划分成最大数不超过k的若干整数之和的方案数

    相当于完全背包中v：1~k 其余1.(6)

3）整数n划分成最小数不小于k的若干整数之和的方案数

    相当于完全背包中v：k~V 其余1.(6)

4）整数n划分成若干不同整数之和的方案数

    相当于01背包恰好等于V(1.(5))

5）整数n划分成k个不同整数之和的方案数

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+6;
const int inf=0x3f3f3f3f3f3f3f3f;
int dp[1100][1100];
void solve()
{
	dp[0][0]=1;
	int n,k;cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		for(int j=i;j>=1;j--)
		{
			dp[i][j]=dp[i-j][j-1]+dp[i-j][j];
		}
	}
	cout<<dp[n][k];
}
signed main()
{
	//ios_base::sync_with_stdio(false);
	//cin.tie(nullptr),cout.tie(nullptr);
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

6） 整数n划分成最大数不超过k的若干不同整数之和的方案数

      相当于01背包中v：1~k 其余1.(5)

7）整数n划分成最小数不小于k的若干不同整数之和的方案数

     相当于01背包中v：k~V 其余1.(5)

8）整数n划分成若干奇数的方案数

     完全背包 v:1 3 5 ...    其余1.(6)

9）整数n划分成若干偶数的方案数

     完全背包 v:2 4 6...    其余1.(6)

3.区间dp

   例题

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+6;
const int inf=0x3f3f3f3f3f3f3f3f;
int a[N],dp[1100][1100];
void solve()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];a[i]+=a[i-1];
	}
	for(int len=1;len<n;len++)
	{
		for(int l=1;l+len<=n;l++)
		{
			int r=l+len;
			dp[l][r]=inf;
			for(int k=l;k<r;k++)
			{
				dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+a[r]-a[l-1]);
			}
		}
	}
	cout<<dp[1][n];
}
signed main()
{
	//ios_base::sync_with_stdio(false);
	//cin.tie(nullptr),cout.tie(nullptr);
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

4.最长上升子序列，最长公共子序列（线性dp)

   例题

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+6;
const int inf=0x3f3f3f3f3f3f3f3f;
int dp[1100][1100];
void solve()
{
	int n,m;cin>>n>>m;
	string s1,s2;cin>>s1>>s2;
	s1=" "+s1;s2=" "+s2;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
			if(s1[i]==s2[j])
			{
				dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
			} 
		}
	}
	cout<<dp[n][m];
}
signed main()
{
	//ios_base::sync_with_stdio(false);
	//cin.tie(nullptr),cout.tie(nullptr);
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

   例题

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+6;
const int inf=0x3f3f3f3f3f3f3f3f;
int dp[1100][1100];
void solve()
{
	int n,m;cin>>n>>m;
	string s1,s2;cin>>s1>>s2;
	s1=" "+s1;s2=" "+s2;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
			if(s1[i]==s2[j])
			{
				dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
			} 
		}
	}
	cout<<dp[n][m];
}
signed main()
{
	//ios_base::sync_with_stdio(false);
	//cin.tie(nullptr),cout.tie(nullptr);
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}