本篇记录动态规划学习时的相关问题,预计花费12天学完,冲冲冲!!!课程为acwing网站。

目录

内容总览

背包问题

0 1 背包

完全背包

三重循环无优化版

优化版本1  --  二重循环二维数组

优化版本2  --  二重循环一维数组

多重背包

多重背包普通版

多重背包之二进制优化 

分组背包

线性DP

数字三角形

最长上升子序列

最长公共子序列

区间DP

内容总览

• 背包问题

• 线性DP

• 区间DP

• 计数类DP

• 数位统计DP

• 状态压缩DP

• 树形DP

• 记忆化搜索

---

背包问题

假设你在小岛上,上面有很多物品,没件物品的价值都不一样,你有一个背包,体积有限,你如何装才能使背包里的物品价值最大呢?(背包不一定能被装满)

0 1 背包

特点:每件物品最多只能用一次

动态规划-01背包问题_一只牛Niu的博客-CSDN博客大佬整理的理解链接：动态规划之01背包问题 - kkbill - 博客园01背包问题 问题描述： 给定 n 件物品，物品的重量为 w[i]，物品的价值为 c[i]。现挑选物品放入背包中，假定背包能承受的最大重量为 V，问应该如何选择装入背包中的物品，使得装入背包中物品的总https://www.cnblogs.com/kkbill/p/12081172.html...https://blog.csdn.net/weixin_53461714/article/details/123927077?spm=1001.2014.3001.5502

完全背包

题目链接https://www.acwing.com/problem/content/3/

特点:每件物品有无限个,只要体积够用就可以装

• 三重循环无优化版

#include
using namespace std;

const int N=1010;
int f[N][N];
int v[N],w[N];
int f1[N];

int main()
{
	int n,m;
	cin>>n>>m;				//输入物品的个数和背包的容量 
	for(int i=1;i<=n;i++)
		cin>>v[i]>>w[i];	//输入每个物品的体积和价值 
	
	//三重循环二维数组 
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			for(int k=0;v[i]*k<=j;k++)
 		   {
				//注意此时与f[i][j]比较 
				f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+w[i]*k);
			}
	cout< 
 
优化版本1  --  二重循环二维数组 
 
 
与01背包的不同点：
 
 
f[i][j]  =  max( f[i][j] , f[i-1][j-v[i]] + w[i] );        //01背包
 
 
f[i][j]  =  max( f[i][j] , f[i][j-v[i]] + w[i] );           //完全背包问题
 因为完全背包的物品可以选无限次
 
 
 
 
 代码：
 
#include
using namespace std;

const int N=1010;
int f[N][N];
int v[N],w[N];
int f1[N];

int main()
{
	int n,m;
	cin>>n>>m;				//输入物品的个数和背包的容量 
	for(int i=1;i<=n;i++)
		cin>>v[i]>>w[i];	//输入每个物品的体积和价值 

	//优化版本1--二重循环二维数组 
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			//不选第i个物品 
			f[i][j]=f[i-1][j];
			//选第i个物品
			//与01背包唯一的不同点就是f[i][j-v[i]]+w[i]
			//因为完全背包第i个物品可以放无限次 
			if(j>=v[i]) 
			{
				f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
			}
		}
	cout< 
 
优化版本2  --  二重循环一维数组 
 
 
与01背包的不同点是逆序遍历体积改为顺序遍历体积；
 
 
因为因为每个物品可以取任意多次，所以不再强求用上一轮的状态，即本轮放过的物品，在后面还可以再放；
 
 
而01背包每次更新需要用到上一轮的状态，为了防止数据被污染，逆序遍历
 
 
代码：
 
#include
using namespace std;

const int N=1010;
int f[N][N];
int v[N],w[N];
int f1[N];

int main()
{
	int n,m;
	cin>>n>>m;				//输入物品的个数和背包的容量 
	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<=m;j++)
		{
			f1[j]=max(f1[j],f1[j-v[i]]+w[i]);
		}
	cout< 
思路来源连接https://www.acwing.com/solution/content/3986/
 
多重背包 
特点:每个物品的个数不一样,第i个物品的个数为s[i]
 
多重背包普通版 
题目链接https://www.acwing.com/problem/content/4/
 
题目：
 
 
 
有 N 种物品和一个容量是 V 的背包。
 
 
第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。
 
 
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
 输出最大价值。
 
 
输入格式
 
 
第一行两个整数，N，V 用空格隔开，分别表示物品种数和背包容积。
 
 
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 ii 种物品的体积、价值和数量。
 
 
输出格式
 
 
输出一个整数，表示最大价值。
 
 
数据范围
 
 
0 0 
 
输入样例
 
 
4 5
1 2 3
2 4 1
3 4 3
4 5 2
 
 
输出样例：
 
 
10
 
 
 分析： 
 
 
 
与完全背包三重循环二维数组差不多，但是多了一个数量限制
 
 
 代码：
 
#include
using namespace std;

const int N=110;
int n,m;				//物品的个数和背包的容量
int v[N],w[N],s[N];		//物品的体积、价值、数量
int f[N][N];

int main()
{
	cin>>n>>m;
	
	for(int i=1;i<=n;i++)
		cin>>v[i]>>w[i]>>s[i];
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			for(int k=0;k<=s[i]&&k*v[i]<=j;k++)
			{
				f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
			}
	cout< 
 
多重背包之二进制优化  
题目链接https://www.acwing.com/problem/content/5/
 
分析：
 
 
 
 
 
 
 
N=15000的原因：题目中N最大为1000，每个物品数量最多为2000，则每个物品最多拆分为1000*log2000个新物品 
 
 
 
 
 代码
 
#include
using namespace std;

const int N=15000;
int n,m;			//物品的个数和背包的容量
int v[N],w[N];		//物品的体积、价值
int f[N];

int main()
{
	cin>>n>>m;
	
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		int a,b,s;	//分别第i个物品的体积，价值和数量 
		cin>>a>>b>>s;
		
		int k=1;		//从1开始分
		while(k <= s)	//凑数 
		{
			cnt++;
			v[cnt]=a*k;
			w[cnt]=b*k; 
			s-=k;
			k*=2;
		}
		if(s>0)
		{
			cnt++;
			v[cnt]=a*s;
			w[cnt]=b*s;
		}
	}
	
	//来一遍01背包 
	n=cnt;	//cnt为我们新组成的物品个数 
	for(int i=1;i<=n;i++)
		for(int j=m;j>=v[i];j--)
			f[j]=max(f[j],f[j-v[i]]+w[i]);
	
	cout< 
分组背包 
特点:物品被分为N组,每一组里只能选择一个物品
 
题目链接https://www.acwing.com/problem/content/9/
 
 题目：
 
 
 
有 N 组物品和一个容量是 V 的背包。
 
 
每组物品有若干个，同一组内的物品最多只能选一个。
 每件物品的体积是 vij，价值是 wij，其中 i是组号，j 是组内编号。
 
 
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
 
 
输出最大价值。
 
 
 
 
输入格式
 
 
第一行有两个整数 N V，用空格隔开，分别表示物品组数和背包容量。
 
 
接下来有 N 组数据：
 
 
每组数据第一行有一个整数 Si，表示第 i 个物品组的物品数量；
每组数据接下来有 Si 行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；
 
输出格式
 
 
输出一个整数，表示最大价值。
 
 
 
 
数据范围
 
 
0 0 0 
 
 
 
输入样例
 
 
3 5
2
1 2
2 4
1
3 4
1
4 5
 
 
输出样例：
 
 
8
 
 
分析：
 
 
 
 一定要搞清楚每层循环要干什么！！不要瞎想乱写
 
 
 
 
二维数组代码：
 
//二维版本
#include
#include
using namespace std;

const int N=110;

int n,m; 
int v[N][N],w[N][N],s[N];
int f[N][N];

int main()
{
	cin>>n>>m;
	
	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++)	//第i组
		for(int j=1;j<=m;j++)	//容量大小
		{
			//不选
			f[i][j]=f[i-1][j];
			//选 第i组第k个，逐个遍历 
			for(int k=1;k<=s[i];k++)
			{
				if(j>=v[i][k])
					f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
				
			} 
		} 
	cout< 
一维数组代码： 
 
#include
#include
using namespace std;

const int N=110； 
int n,m;
int v[N][N],w[N][N],s[N];
int f[N];

//直接写成一维版的
//我们只要记住如果用到了上一轮的状态，则逆序遍历体积
//如果只用到了本轮的状态，则顺序遍历体积 
int main()
{
	cin>>n>>m;
	
	//i为第几组，j为组内第几个物品 
	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=m;j>=0;j++)			//枚举容量大小 
			for(int k=1;k<=s[i];k++)  	//枚举选择每组的第几个数 
			{
				if(v[i][k]<=j)
					f[j]=max(f[j],f[j-v[i][k]]+w[i][k]); 
			}
	cout< 
 
 

线性DP 
数字三角形 
题目链接https://www.acwing.com/problem/content/900/
 
题目：
 
 
 
给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。
 
 
        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5
 
 
输入格式
 
 
第一行包含整数 n，表示数字三角形的层数。
 
 
接下来 n 行，每行包含若干整数，其中第 i 行表示数字三角形第 i 层包含的整数。
 
 
输出格式
 
 
输出一个整数，表示最大的路径数字和。
 
 
数据范围
 
 
1≤n≤500
 −10000≤三角形中的整数≤10000
 
 
输入样例：
 
 
5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5
 
 
输出样例：
 
 
30
 
 
分析： 
 
 
 
有两种思路：
 
 
正序dp： 
   
此时需要开两个二维数组f[i,j]和a[i,j]，一个用来记录路径的最大值，一个用来记录输入的每点的权值
需要处理边界问题，因为题目中有负数，所以需要把边界都置为负无穷，再将dp数组第一个值赋初值，即f[1,1]=a[1,1]
写时一定要注意数组赋值时边界为多少！！
倒叙dp：不需要处理边界问题，一个f数组就可以搞定，但比较难想到
 
代码：
 
正序： 
#include
#include

using namespace std;

const int N=510,INF=1e9;
int f[N][N];	//表示从起点走到(i,j)的最大加权值 
int a[N][N];	//每个点上的值 
int n;
 

int main()
{
	cin>>n;
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i;j++)
		{
			cin>>a[i][j];
		} 
		
	//为了避免边界问题，即防止某点的值为负值与边界进行比较时 
	for(int i=0;i<=n;i++)
		for(int j=0;j<=i+1;j++)    //初始时确保边界都初始成功
		{
			f[i][j]=-INF;
		} 
	f[1][1]=a[1][1];
	

	for(int i=2;i<=n;i++)    //从第二行开始
		for(int j=1;j<=i;j++)
		{
			f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j];
		}
	
		
	int res=-INF;	//用来保存答案		
	for(int i=1;i<=n;i++)
		res=max(res,f[n][i]);	
	cout< 
倒序： 
#include
#include
using namespace std;

const int N=510;
int  f[N][N];
int n;

int main()
{
	cin>>n;
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i;j++)
			cin>>f[i][j];
			
	for(int i=n;i>=1;i--)
		for(int j=1;j<=i;j++)
		{
			f[i][j]=max(f[i+1][j],f[i+1][j+1])+f[i][j];
		}
		
	cout<  

 
最长上升子序列 
acw-895.最长上升子序列https://www.acwing.com/problem/content/897/
 
 题目详情：
 
 
 
给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。
 
 
 
 
输入格式
 
 
第一行包含整数 N。
 
 
第二行包含 N 个整数，表示完整序列。
 
 
 
 
输出格式
 
 
输出一个整数，表示最大长度。
 
 
 
 
数据范围
 
 
1≤N≤1000，
 −1e9≤数列中的数≤1e9
 
 
 
 
输入样例：
 
 
7
3 1 2 1 8 5 6
 
 
输出样例：
 
 
4 (即1 2 5 6)
 
 
 分析
 
 
 
f[i]：为当前状态即第i个数为结尾的最长上升子序列的长度，初始值f[i]=1，i∈[0,n-1]，表示自己就是最长上升子序列，长度为1
 
 
 
 
状态转移：把前 i-1 个数字中所有满足条件（w[j] 
 
 
 
eg 5 9 12 4 6 17这个序列，求f[5]，f[3]=3，f[4]=1，w[4] 
 
 
 
 
 
 
 
代码：
 
#include
#include
using namespace std;

const int N=1010;

int n;
int w[N],f[N];

int main()
{
	cin>>n;
	for(int i=0;i>w[i];
	 
	for(int i=0;i 
扩       展： 假如我们要把最长上升子序列保存下来，如何保存呢？
 
解决办法： 加一个g[N]数组，将每次的状态转移记录下来
 
 
代码：
 
//扩展：将最长子序列保存下来
#include
#include
using namespace std;

const int N=1010;

int n;
int w[N],f[N];
int g[N];	//保存最长子序列 

//先求f[i]的最长上升子序列，如果a[j]>a[i]，则
int main()
{
	cin>>n;
	for(int i=0;i>w[i];
	  
	for(int i=0;i 

最长公共子序列 
 
 
给定两个长度分别为N和M的字符串A和B，求既是A的子序列又是B的子序列的字符串长度最长是多少。（不需要在序列中连续但顺序相同）
 
 
示例数据(来源于acwing)：
 
 
4 5 
 
 
acbd
 
 
abedf
 
 
输出：
 
 
3
 
 
分析：
 
 
 
 
 
 后面三种情况往往包含第一种情况，所以在代码中不体现
 
 
代码：
 
#include
#include

using namespace std;

const int N=10010;
int  n,m;
char a[N],b[N];
int f[N][N];

int main()
{
	cin>>n>>m;
	scanf("%s%s",a+1,b+1);	//相当于a[0],b[0]没存字符 

	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			//第二种和第三种情况 01 10 
			f[i][j]=max(f[i-1][j],f[i][j-1]);
			//第四种情况 11 
			if(a[i]==b[j])
				f[i][j]=max(f[i][j],f[i-1][j-1]+1);
		}
		 
	cout< 
 
 

区间DP 
石子合并 
 题目详情：
 
 
 分析：