动态规划的一个初步学习

啥叫动态规划

在我们写很多的题目时，常常可以用暴力枚举来写，缺点就是速度太慢了。如果我们用一个数组或者哈希表（虽然我还没学过哈希表）将之前暴力枚举的数据储存起来，当再一次枚举到这个数字的时候就直接调用数组或者哈希表里面的数据，这样就能节省很多时间。所以动态规划就是带数组记忆的递归，所以动态规划也往往叫做记忆化搜索。

1.状态转移方程是啥：状态转移方程根据我的理解就是，可以根据前面的一维数组（或者二维数组）推出接下来的数组中的值，优点类似于数学里面的数列里面的递推公式，在动态规划里面比较核心的的就是想出其递推公式，想出来后题目也会变得通透的多。

做动态规划的五步骤

1.dp数组以及下标的含义。
2.递推公式。
3.dp数组的初始化。
4.遍历顺序。
5.打印dp数组

01背包问题

优化前：用一个二维数组来存放数据。优化后：用一个一维数组来存放数据（所以01背包也是由相对固定的模板的）

优化前：二维数组进行存储
首先根据5步曲来，分析一下dp数组的含义：下标为0到i之间的物品（不同的物品有着不同的价值），任取放进容量为j的背包里面,而dp数组的具体值就是放进去这个物品的最大价值。

递推公式：不放物品：dp[i-1][j];
                      放物品：dp[i-1][j-wight[i]]+value[i];(这个value[i]就是i这个物品的价值，同时还要声明一下，这里其实还要做一下判断，看是否有超过背包的最大容量)

最终的模样:dp[i][j]=max(dp[i-1][j],dp[i-1][j-wight[i]]+value[i]);

dp数组的初始化：需要将第一个物品那一行给初始化，其他的都初始化为0.

优化后：使用滚动数组也就是使用一维数组来实现价值最大化   
形象一点就是将这个二维矩阵压缩，或者是将这个贴在一个圆柱上，每次进行到下一个物品的时候就将这个圆柱转一下就切换到下一个物品了。
含义：dp数组里面存放的依然是物品的价值，而下标就是和未优化前的二维数组中的j一样：容量为j的背包所能装的最大价值为dp[j];

递归公式：dp[j]=max(dp[j],dp[j-wight[i]]+value[i]); 这个就是相当于将前一个物品给拷贝过来一份，所以在这里的dp[j]就是相当于前一层的数据。

 列题

过河卒

 做动态规划最重要的就是推出其递推公式，一般很难想到，所以这里建议先在二维数组先写几个数，然后看看这些数之间有没有什么关系（数学归纳法：先写出来几个看看这些数字有啥关系，然后如果找到规律了就直接使用）
（该图来自b站up：LetsLearning）

写几个数字就能发现，在没有马的情况下二维数组中的每一个数的值都是由它的上面和左边加构成，所以通过这里就可以的得到递推公式;a[i][j]=a[i-1][j]+a[i][j-1]; 

接下来就是加上马的干扰，我们先将整个棋盘全部初始化为1（这样做的目的是为了将0行和0列初始化为1，方便接下来的操作），我们用一个方向数组（这个数组里面记载的是马的行走规则，集“日”字型走），用一个for循环将马走到的地方全部初始化为0，这样进行递推的时候就方便进行加，如果加上马的话就需要堆递推进行一点小改动，主要就是体现在第0行和第0列的改动，这个时候第0行和第0列的的递推公式就要改成    a[i][j]=a[i][j-1];    a[i][j]=a[i-1][j]; ,因为马做过的地方的左边和上面都不能走，如果马的这个地方为0，那么后面相加的时候也会为0，就不会对后面的造成影响。
代码如下（中间这些被注释掉的没有必要看，就是用来检查我有没有做对）（对了a数组要开long long类型的，不然有些数据会过不了）

#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll a[35][35];
int n,m;
int x,y;
int dx[9]={0,-1,-2,-2,-1, 1, 2, 2,1};
int dy[9]={0,-2,-1, 1, 2,-2,-1, 1,2};
int main()
{
	//初始化为1
	cin>>n>>m>>x>>y;
	for(int i=0;i<=n;i++){
		for(int j=0;j<=m;j++){
			a[i][j]=1;
		}
	}
	//马的存在
for(int i=0;i<=8;i++){
	int tx=x+dx[i];
	int ty=y+dy[i];
	if(tx<0||tx>n||ty>m||ty<0)
	continue;
	else
	a[tx][ty]=0;
}
//检查二维数组
//	for(int i=0;i<=n;i++){
//		for(int j=0;j<=m;j++)
//		printf("%5d ",a[i][j]);
//		printf("\n");
//	}
//接下来就是递推公式
	for(int i=0;i<=n;i++){
		for(int j=0;j<=m;j++){
			if(i==0&&j==0)
			continue;
			if(a[i][j]==0)//这个点是马走过的，那这里的值就不能走，就应该为0，由于之前我们已经将马走过的地方赋值为0，所以是可以跳过的
			continue;
			if(i==0)
			a[i][j]=a[i][j-1];
			else if(j==0)
			a[i][j]=a[i-1][j];
			else
			a[i][j]=a[i-1][j]+a[i][j-1];
		}
	}
//检查二维数组
//	for(int i=0;i<=n;i++){
//		for(int j=0;j<=m;j++)
//		printf("%5d ",a[i][j]);
//		printf("\n");
//	}
	cout<<a[n][m]<<endl;
	return 0;	
}

守望者的逃离

思路：先讲一遍不用动态规划来写的方法，我么用一个s1和s2分别代表着不用闪现走的路程，和用闪现走的路程，两边同时开弓。每次进行完一次计算都需要将s1和s2进行一次比较将大者的值赋给s1（由于s1是最特殊的，最后我们输出的变量的值也是s1的值）（其实使用动态规划也是使用这样一个思路）其中这里面很巧妙的思路就是使用一个for循环来代表时间的推进还有使用s1,s2两边同时开工，然后这个路程的取值往往都是取最大（我还没学过贪心）。

代码如下：

#include<iostream>
using namespace std;
int m,s,t;
int main()
{
	cin>>m>>s>>t;
	int s1=0,s2=0;
	for(int i=1;i<=t;i++)
	{
		s1+=17;
		if(m>=10){
			s2+=60;
			m-=10;
		}
		else{
			m+=4;
		}
		if(s2>s1)s1=s2;
		if(s1>=s){
			cout<<"Yes"<<endl;
			cout<<i<<endl;
			return 0;
		}
	}
	cout<<"No"<<endl;
	cout<<s1<<endl;
	return 0;
}

接下就是讲解使用dp数组求解：
思路：和上面的思路其实一样，在这里我感觉到动态规划就是要使用前一个数组元素的值来进行求解（及最关键的就是看大问题是否能够被小问题推出，如果已经看出来这一点那么递推公式也就能写出来了），先将dp数组全部用闪现的方式记录每一秒的运动路程。在进行完全部过程后再使用一个for循环来检查就用看是dp[i]大还是dp[i-1]+17大，如果是后者大那么就将这个值赋给dp[i]（我怎么感觉有一点01背包的思想在里面）.

#include<iostream>
using namespace std;
int dp[500000000];
int main()
{
	int m,s,t;
	cin>>m>>s>>t;
	for(int i=1;i<=t;i++)
	{
		if(m>=10)
		{
			dp[i]=dp[i-1]+60;
			m-=10;
		}
		else
		{
			dp[i]=dp[i-1];
			m+=4;
		}
	}
	for(int i=1;i<=t;i++)
	{
		if(dp[i]<dp[i-1]+17)
		dp[i]=dp[i-1]+17;
		if(dp[i]>=s)
		{
			printf("Yes\n%d",i);
			return 0;
		}
	}
	printf("No\n%d",dp[t]);
	return 0;
}