动态规划可能是算法里边最难的,也可能是机试里最难的,所以作为小白,最好是能积累,丰富自己的题库,以下是我在刷保/考研究生机试题的动态规划的内容,都比较简答,以后遇到类似题目还会不断更新。

感谢计算机机试群里的大佬提供我们练习的机会。群号:299565515

一、走楼梯问题

动态规划问题虽然代码比较简单,但是在构造递推式时候是最难的,这个题的递推式大家肯定都做过,没错,就是斐波那契数列的递推式。F(n)=F(n-1)+F(n-2)。

为什么是这样呢?

首先我们可以从最后一层楼梯考虑。假设有10层台阶,那么每次只能走一层台阶或者两层台阶的话,我可以从第8层台阶和第9层台阶走到第10层台阶。也就是说 第10层台阶的走法数=第8层台阶的走法数+第9层台阶的走法数

即F(10)=F(8)+F(8)。因此就推导出了我们的推导式。那么动态规划的边界是哪儿呢?

通过分析题意,我们可以看到,我们处于第一级,所以F(1)=0,F(2)=1,F(3)=2,这些都是很容易得到的,有了这些,我们就可以写代码了。

#include<iostream>
using namespace std;
const int n=40;
int F[n]; 
int main()
{
	int M;
	while(cin>>M)
	{
		F[1]=0;F[2]=1;F[3]=2;
		for(int i=4;i<=M;i++)
			F[i]=F[i-1]+F[i-2];
		printf("%d\n",F[M]);
	}
	return 0;
}

二、最长子列和问题

最长子列和问题可以说是最常见的动态规划问题了,我至少见过3次。

这个问题有很多种解法,包括暴力的方法,分治思想的递归方法,还有动态规划方法等。

下边我主要介绍暴力和动态规划的方法,因为暴力当时没有过,所以采用动态规划的方法,后来过了。

1.暴力:

这道题是寻找最长子序列串,并且找出构成最长子序列串的首个数字和最后一个数字。

我的思想是可以通过遍历依次寻找,第一次可以只找一个数字,然后遍历一圈数组,找出最大的存起来,第二次可以找两个数字作为一组,然后类似滑动窗口对数组进行遍历,然后最后到string.size()这么长的数字作为一组(只有一个)

方法很通俗易懂,但是时间复杂度比较高。O(n的3次方)。

代码如下:

void baoli()
{
	int beg,ed,max=-99999,record=0;
	int flag1,flag2;
	for(int i=1;i<=n;i++) //n种窗口大小 
	{
		for(int j=0;j+i<=n;j++)
		{
			int k;
			for(k=j;k<j+i;k++)
				record+=vec[k];
			if(record>max ||(record==max&&(j<=flag1&&j+i-1<=flag2)))
			{ 
				max=record;
				beg=vec[j];
				ed=vec[j+i-1];
				flag1=j;
				flag2=j+i-1;
			}
			record=0;
		} 
	}
	printf("%d %d %d\n",max,beg,ed);
} 

 2.动态规划

这个题的动态规划是最难想的,也是时间复杂度最低的吧。

我们可以这样表示,dp[i]表示,以dp[i]结尾的元素的最长子序列和

通俗来说就是,dp[i]存储的是i和i前的最长子序列和,有人说了,如果i后边是正数,那么相加肯定比dp[i]大,这个就不用i这层去考虑了,dp[i+1]层自然会考虑进去,通过分析,我们发现,dp[i]=max{dp[i-1]+a[i],a[i]},     a[i]表示数组中存的输入的子序列。

当前的最长子序列和=上一层的最长子序列和+数组中的当前层的 数和 当前单个数的中间的最大值。

代码如下:

const int maxn=10010;
int in[maxn],dp[maxn];//dp[i]表示以dp[i]结尾的最大子序列和 
int p[maxn][2];
void dpway()
{
	dp[0]=in[0];
	p[0][0]=in[0];p[0][1]=in[0];
	for(int i=1;i<n;i++)
	{
		if(in[i]>=dp[i-1]+in[i])
		{
			dp[i]=in[i];
			p[i][0]=in[i];
			p[i][1]=in[i];
		}
		else
		{
			dp[i]=dp[i-1]+in[i];
			p[i][0]=p[i-1][0];
			p[i][1]=in[i];
		}
	}
	int max=-99999;int left=0;int right=0;
	for(int i=0;i<n;i++)
	{
		if(max<dp[i])
		{
			max=dp[i];
			left=p[i][0];
			right=p[i][1];
		}
	}
	printf("%d %d %d\n",max,left,right);
}