算法入门经典竞赛第二版动态规划（抽象篇）

96 阅读 0 评论 64 点赞

我是靠谱客的博主友好草莓，这篇文章主要介绍算法入门经典竞赛第二版动态规划（抽象篇），现在分享给大家，希望可以做个参考。

1抽象的动态规划

a.何为抽象的动态规划，就是用dp[i][j]i表示一个数，j表示另一个数，然后思考状态转移；
例题：出栈顺序
思路：
f(i,j)表示出栈顺的总数：
i表示为栈外的车数,j表示栈内的车数;
由2种状态:注意状态表示不能跳跃
状态跳跃就是这个状态转移后又转移到下一个状态：
这题有2种情况：
一：里面的车出去一辆，外面不进来；
二：里面的车不出去，外面进来一驾车；
跳跃就是里面的车出去，外面进来一辆；
仔细观察会发现这个情况就是一二合在一起的情况
公式：

复制代码

1
2
3
f[i][j]+=dfs(i,j-1);//外面进来，里面出去一个
	 f[i][j]+=dfs(i-1,j+1);//外面进来一辆

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<cstdio>
#define MAX_N 20
#define ll long long
using namespace std;
int n;
ll f[MAX_N][MAX_N];
ll dfs(int i,int j)//i表示栈外的数量 ,j是栈内的车数 
{
	if(f[i][j]) return f[i][j];//如果记忆化搜索里面有值的话就直接返回；
	if( i == 0 ) return 1;//如果栈外里面没车了，就放回1，栈内全部出去
	if(j > 0 ) f[i][j]+=dfs(i,j-1);
	 f[i][j]+=dfs(i-1,j+1); 
	return f[i][j];
}
int main()
{
	scanf("%d",&n);
	printf("%lld",dfs(n,0));
	return 0;
}

总结：
这里运用到一个刘佳汝老师说的记忆化搜索技巧：
每次递归的时候，画出搜索树的时候会有状态计算重复，比如说f（1，2）在f(2,1)的时候和f(1,3)的时候都调用过了，每次调用都要重复计算浪费时间；不如把计算过的数值保存下来；
用一个数组保存

复制代码

1
2
3
ll f[MAX_N][MAX_N];
	if(f[i][j]) return f[i][j];//如果之前计算过的话，就直接返回

边界处理:

复制代码

1
2
3
4
if(j > 0 ) f[i][j]+=dfs(i,j-1);//如果j大于0的话，就可以从j-
1转移：
	 f[i][j]+=dfs(i-1,j+1);

方法二
递推：
思路：

1，状态表示：dp[i][j] i表示栈内的数，j表示栈外的数；
2.边界化：i==j dp[i][j]=dp[i][j-1];//如果栈内和栈外的方案，就里面不动，外面进来一个
3. 初始化 dp[i][0]=1; 外面没车了，里面出去一个就好了
公式：
dp[i][j]=dp[i-1][j]+dp[i+1][j-1]

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <iostream>
using namespace std;
long long  dp[10010][10010];//i是栈外的车，j是栈内的车 
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<=n;++i)
	{
		dp[0][i]=1;
	}
	
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j)
		{
			if(j==0) //栈内没车 
			{
				dp[i][j]=dp[i-1][1];
				continue;
			}
			if(i==j) dp[i][j]=dp[i-1][j];
			else dp[i][j]=dp[i][j-1]+dp[i-1][j] ;
		}
	}
	cout<<dp[n][n]<<endl;
	return 0;
}

2.题目：
一个游戏每个人都可以给左边或者右边的人可以由左边到右边的人转过来：
思路：
1.抽象表示出来，dp[i][j]表示考虑第i圈到第j个人手里：

2.公式：dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1];//每次都是上一圈考虑前面一个和上一圈后面一个人
3.初始化:dp[0][1]=1;转了0次，表示第1个人;
4.边界化：
if(j == 1) 1号人是上一次的2号和n 号过来
else if(j == n) n号人是上一次1号和n-1号过来；
5，答案是表示为：
dp[m][1]；
6.循环顺序：i-1先完成i从小到大完成：
代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <iostream>
using namespace std;
long long dp[10010][10010];
int main()
{
	int n,m;
	cin>>n>>m;
	dp[0][1]=1;
	for(int i = 1;i<= m;++i)
	{
		for(int j = 1;j <= n;++j)
		{
			if(j == 1)
			{
				dp[i][j]=dp[i-1][2]+dp[i-1][n];
			 } 
			 else if(j == n)
			 {
			 	dp[i][j]=dp[i-1][1]+dp[i-1][n-1];
			 }
			 else
			 dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1];
		}
	}
	cout<<dp[m][1]<<endl;
	return 0;
}

3.题目；
有个珠子每个珠子可以和前面后面的合并，合并后该位置变为前后2个珠子合并的乘积：
求最大值：
比如输入：
8
-9 -5 - 4 -2 4 -5 -4 2
输出 73；
思路：
1.dp[i][j]表示考虑到i这个位置，j表示状态 0 是不合并，1是合并；
2.公式：
dp[i][0]不合并的话就是可以顺便搞，选前面最大值就可以dp[i][0]=max(dp[i-1][0],dp[i-1][1])
dp[i][1]//合并的话就是当前加上乘积

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
int dp[10010][2];
int w[10010];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;++i)
	{
		cin>>w[i];
	}
	dp[1][0]=0;
	for(int i=2;i<=n;++i)
	{
		dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
		dp[i][1]=dp[i-1][0]+w[i]*w[i-1];
	}
	cout<<max(dp[n][0],dp[n][1])<<endl;
	return 0;
	
}