计算机机试一动态规划例题总结(适合入门)

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

感谢计算机机试群里的大佬提供我们练习的机会。群号：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);
}