动态规划可能是算法里边最难的,也可能是机试里最难的,所以作为小白,最好是能积累,丰富自己的题库,以下是我在刷保/考研究生机试题的动态规划的内容,都比较简答,以后遇到类似题目还会不断更新。
感谢计算机机试群里的大佬提供我们练习的机会。群号: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);
}