最近主要学习了动态规划
一、理解
动态规划主要是将一个复杂问题划分为子问题,通过子问题的最优解求得源问题的最优解。在做题中最重要的就是通过思考建立动态规划方程,找到合理的子问题逐步递推出整个问题,其次就是要注意初始值,很多dp数组都用到i-1这样的方程,所以应该在循环外定义dp[1] 循环则从2开始
二、一些入门的例题
一维动态规划:
1.求最长子序列
首先用dp[1]取出第一个数,然后从第二个数开始依次与左边的数比较,找出每个位置的子序列长度,最后整个比较出最长子序列
核心部分
for(i=2;i<=N;i++)
{ int temp=0;
for(j=1;j<i;j++)
{ if(b[i]>b[j])
{ if(temp<amaxlen[j])
temp=amaxlen[j];
}
}
amaxlen[i]=temp+1;
}
光比较这个位置的数和左边的数大小是不够的,比如 1 4 3 5 还要用temp在循环进行到1 4 3的时候使temp和amaxlen进行比较 这样5虽然大于3 但是temp值却没变,所以最长长度得出3
2.求上升子序列中和最大的一个
我在之前的题中得到经验,也是依次往下取每个位置的最大和,后一个则加上前一个位置的最大和,最后在比较每个位置的最大和得出答案,编写了一个冗杂程序
#include <iostream>
#include <algorithm>
#include <string.h>
#include <cmath>
using namespace std;
int main()
{ int i,j,n,max=0;
int a[1010],temp[1010],sum[1010];
while(1)
{ cin>>n; if(n==0) break;
memset(temp,0,sizeof(temp));max=0;
memset(sum,0,sizeof(sum));
for(i=1;i<=n;i++)
{ cin>>a[i];
}
sum[1]=a[1];
temp[1]=a[1];
for(i=2;i<=n;i++)
{ for(j=1;j<i;j++)
{ if(a[i]>a[j])
{ temp[i]=sum[j]+a[i];
if(temp[i]>=sum[i]) sum[i]=temp[i];}
else{temp[i]=a[i]; if(temp[i]>sum[i]) sum[i]=temp[i];}
}
}
for(i=1;i<=n;i++)
{ if(sum[i]>=max) max=sum[i];
}
cout<<max<<endl;
}
}
首先从i向左依次比较,用if不断比较来记下前面和的最大值,如果满足比较条件则下一个位置可以加上上一个位置的最大和,但是子序列可能会突然出现一个非常大的数,使这个位置上的最大和不能包括这个数,但这个数却恰恰只凭自己便比之前累加的最大和还要大,这样就要考虑a[i]小于a[j]但序列和最大的情况,所以将其赋值到temp中与其他和比较得出最大的sum,最后在比较每个位置上的sum相比较即可得出总的上升子序列的最大和
二维动态规划:
3.给出一段数字依次加减一个数字最后得出最大值
这个需要用到二维数组,既要加到最大的数也要减到最小的数,则用[][0]表示需要加数了,用[][1]表示需要减数了
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int a[150005][2];
int m,i,n;
while(cin>>m)
{ a[0][0]=a[0][1]=0;
for(i=1;i<=m;i++)
{ cin>>n;
a[i][0]=max(a[i-1][0],a[i-1][1]-n);
a[i][1]=max(a[i-1][1],a[i-1][0]+n);
}
cout<<max(a[m][0],a[m][1])<<endl;}
}
核心程序的第一行来比较减去i和i+1后谁更大,取其,第二行比较加上i和i+1后谁更大,一直递推下去得到最后的最大值。
滚动数组动态规划:
每次使用固定的几个存储空间让数组滚动起来,达到压缩,节省空间的作用,主要应用在递推或动态规划中,dp很多题是向上扩展的过程,前面的解可以省去,能达到更好的优化效果
4.斐波那契数列
本要用a[i]=a[i-1]+a[i-2]才能实现,利用滚动则可以得到一个稳定的式子a[2]=a[0]+a[1],循环则把两个数依次赋给a[0]和a[1]即可
题目1.2子序列问题的展示解法都是求出每个位置的最大值,然后在整个循环里比较出他们之中最大的那个,而题目3则运用了递推一步步将最大值推向最后,则是滚动数组
三、了解的知识
1.有些题目需要输入大量测试数据,则需要freopen函数来解决测试数据输入问题
freopen("in.txt","r",stdin);
第一个参数是文件名,第二个参数是文件打开模式,第三个参数是一个文件,通常指标准流文件。其中stdin是标准输入流,默认为键盘;stdout是标准输出流,默认为屏幕;stderr是标准错误流,一般把屏幕设为默认。
2.更快的编写出程序,则运用#difine进行宏定义
四 感悟
通过两个周的学习,我大致了解了动态规划和一些做题思路,可以明显地感觉到动态规划比贪心算法难度上升了很多,在做贪心算法的题目时,感觉大方向其实只有一条线,让思路一条路走到头就可以了,但是动态规划想要构造出动态方程,有时感觉脑海中有几条线在同时进行,经常想着想着就短路了。我现在只能做出小部分一维动态规划。像递推等方法理解但完全不会运用,甚至比较难的题题解看很久都无法理解它的意思
还需要练习很多的题,掌握各种题型总结出大概规律,也要多学习他人的思路来优化自己的代码,最重要的还是要调整好心态,不气馁不放弃,收获达到一定程度时一定会有质一样的飞跃。