这几天在学动态规划，先没弄懂怎么把一个问题合理的划分成子问题，先记录一下这几天做的几个题
1.

这道题的实质就是求最长递减子序列
这个思路就是
我们从第一个数开始以次求出以他结尾的最长子序列最求看最大是哪个。
我们用一个数组dp来记录最大递减子序列，dp【i】表示以第i个字符结尾。
先假设一下，现在在求第i个的序列长，那么我们前面的都已经保存着他们对应的子序列长，如果要以这个结尾，那么他就要小一点，所以找到前面比我们这个数大的，然后要考虑的就是我们接不接到这个后面，我们假设这是我们找到的第一个，（一开始初始化的时候我们dp保存的都是1，他们本身就是一个序列），我们肯定是接到后面的，当我们找到第二个的时候，我们要考虑接不接的时候，就是判断我们是接了子序列大点，还是不接的大点，所以状态转移方程就是dp【i】=max（dp【i】，dp【j】+1）；
AC代码

#include<stdio.h>
#define max(x,y) x>y?x:y
int n,dp[101],a[101];
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;//初始化都为1
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<i;j++)
		if(a[i]<=a[j])//当前的数小于前面的数
		dp[i]=max(dp[i],dp[j]+1);
	}
	int num=0;
	for(int i=1;i<=n;i++)
	if(dp[i]>num) num=dp[i];//找出最长的
	printf("%d\n",num);
	return 0;
}

01背包
01背包特点是他的东西只有一个，所以只要考虑放不放
先来二维的。然后进行降维，和常数级优化
二维的时候我们用dp【i】【j】表示把前i个放到容量为j的背包里面。
因为背包不要求放满，所以我们初始化为全0，如果要求放满就是除了dp【0】【0】是0其他的都是负无穷。
这个理解的话就是，不要求放满的话，我们没放满也可以，所以都可以为0，也是可以的。
如果放满那么我们只有容量为0的才可以用0放满，而其他的如果是0，但是容量不是0，所以没放满，是不允许的，我们就设为负无穷。
当放一个东西时，我们主要是考虑放不放，而这个依据就是2中情况的价值看那个大点，那么方程出来了
dp【i】【j】=max（dp【i-1】【j】，dp【i-1】【j-v【i】】+w【i】）
这里dp【i-1】【j】就代表我们不放的最大价值，就是我们前i-1个放到这个j容量的最大价值
dp【i-1】【j-v【i】】+w【i】就是我们放的最大价值因为我们要放进这个东西，所以容量要为j-v【i】。
AC代码

#include<stdio.h>
#define max(x,y) x>y?x:y
int dp[1005][1005],w[1005],v[1005];
int n,m;
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]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
		else dp[i][j]=dp[i-1][j];
	}
	printf("%d\n",dp[n][m]);//最后我们这个状态就是我们的解
	return 0;	
} 

空间优化，降维
刚刚用的是2维的，现在要改写成一维的，我们把行去掉，我们保证我们做完第某件物品后，我们这个数组保存的就是我们这个物品的在0到j容量包里的最大价值
当放i的物品的时候我们需要就是二维数组的方程里面的dp【i-1】【j】和dp【i-1】【j-v【i】】，因为我们一维的当前数组，就是保存的i-1的价值，所以我们就不需要i-1了，又因为，我们只受前面的影响，所以在我们保存第i个物品的最大价值的时候，我们要从后面开始改变，也就是我们j的变化范围是：背包容量->0；
又因为，我们的容量要放得下这个物品，如果放不下的话，就是上一次价值，这里的话，就直接可以把j的变化范围变成：背包容量->当前物品的重量。
状态方程也就是dp【j】=max【dp【j】，dp【j-v【i】+w【i】】；
AC代码

#include<stdio.h>
#define max(x,y) x>y?x:y
int dp[1005],w[1005],v[1005];
int n,m;
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\n",dp[m]);
}

常数级优化
因为我们只需要dp【m】的值，然后依次往前推
当我到n-1个物品的时候我们推出dp【m】，只需要dp【m】和dp【m-v【n】】，所以我们的关键在于dp【j-v【n】】
再往前推的话，就可以发现我们的j只要到max（v【i】，m-sum（v【i+1】到v【n】））
这样如果后者大于前者，就代表我们的j就只要走到后者哪里就可以推出dp【m】了，如果前者大于后者就代表我们不能这样，但是我们j又必须》=v【i】，所以就是v【i】。关于求和可以使用前缀和，优化时间，就不会超时。
AC代码

#include<stdio.h>
#define max(x,y) x>y?x:y
int dp[1005],w[1005],v[1005],s[1005];
int n,m;
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
	{
	scanf("%d %d",&v[i],&w[i]);
	s[i]=s[i-1]+v[i];
	}
	for(int i=1;i<=n;i++)
	{
		int num=max(v[i],m-(s[n]-s[i]));//s【n】-s【i】就是i+1到n的物品质量和
		for(int j=m;j>=num;j--)
		dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
	}
	printf("%d\n",dp[m]);
}

下面就都是1维的了
2.完全背包
特点：东西有无限多，想放几个放几个
这个有基本思路，就是一件物品最多只有m/v【i】个，我们就再放的时候对一种物品放很多个的也跑一遍，这个的时间复杂度是O（n*sum（m/v【i】））
记录一下O（mn）的
对与我们的01背包，我们为什么从m开始？就是为了，我们的值都是有前面的物品价值推出来的，方程是max（dp【i-1】【j】，dp【i-1】【j-v【i】】+w【i】}），而我们完全背包的方程是的max（dp【i-1】【j】，dp【i】【j-v【i】】+w【i】），这里的变化就是后者，因为可以多放，所以我们就不用靠上一次能放下这个东西的最大价值了，我们就直接看我们放了这个物品的。我一开始纠结在，为什么就确保我们放了这个的价值比上一个这里的价值大呢或者相等呢，原来我们在前面的时候如果到了这里，他就会在这里保存一个比上那个大于或者等于的值，最后把这个方程变为1维的。
AC代码

#include<stdio.h>
#define max(x,y) x>y?x:y
int dp[1005],w[1005],v[1005];
int n,m;
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\n",dp[m]);
	return 0;
}

其实这个也可以二进制优化，先看代码，下面讲二进制优化。

#include<stdio.h>
#define max(x,y) x>y?x:y
int dp[1005],w[1005],v[1005];
int n,m;
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++)
	{
		int num=m/v[i],flag=1,k=1;
		while(flag)
		{
			if(k>num) 
			{
				flag=0;
				k=num;
			}
			num-=k;
			for(int j=m;j>=v[i]*k;j--)
			dp[j]=max(dp[j],dp[j-k*v[i]]+k*w[i]);
			k<<=1;
		}
	}
	printf("%d\n",dp[m]);
	return 0;
}

3，多重背包
多重背包就说二进制优化后的把
我们把多重背包转换成01背包，让他的问题变成放和不放。
因为他们的区别就是物品数量不一样，那么我们就将这种物品按照数量给他进行划分
二进制思想的话，就是假设我们这这种物品的数量为7，那么我们把他按照数量分为不同价值，不同重量的东西，划分成数量分别为1,2,4,个的东西，这样我们考虑这几个东西的放和不放的话，就相当于有3位的二进制，他每一位取不取1，我们就可以表示出了0到7的情况，如果不能用二进制表示完，我们就尽可能的表示出来，比如8，我们就分为1,2,4,1这样会优化很多时间，时间从O（nsum(p【i】））到O（nsum（log（p【i】））。
AC代码

#include<stdio.h>
#define max(x,y) x>y?x:y
#define min(x,y) x>y?y:x
int dp[2005],v[1005],w[1005],s[1005];
int n,m;
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++)
	{
		int num=min(s[i],m/v[i]),flag=1,k=1;
		while(flag)
		{
			if(k>num) 
			{
				flag=0;
				k=num;
			}
			num-=k;
			for(int j=m;j>=v[i]*k;j--)
			dp[j]=max(dp[j],dp[j-k*v[i]]+k*w[i]);
			k<<=1;
		}
	}
	printf("%d\n",dp[m]);
}