最近主要学习了动态规划
一、理解
动态规划主要是将一个复杂问题划分为子问题，通过子问题的最优解求得源问题的最优解。在做题中最重要的就是通过思考建立动态规划方程，找到合理的子问题逐步递推出整个问题，其次就是要注意初始值，很多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进行宏定义
四 感悟
通过两个周的学习，我大致了解了动态规划和一些做题思路，可以明显地感觉到动态规划比贪心算法难度上升了很多，在做贪心算法的题目时，感觉大方向其实只有一条线，让思路一条路走到头就可以了，但是动态规划想要构造出动态方程，有时感觉脑海中有几条线在同时进行，经常想着想着就短路了。我现在只能做出小部分一维动态规划。像递推等方法理解但完全不会运用，甚至比较难的题题解看很久都无法理解它的意思
还需要练习很多的题，掌握各种题型总结出大概规律，也要多学习他人的思路来优化自己的代码，最重要的还是要调整好心态，不气馁不放弃，收获达到一定程度时一定会有质一样的飞跃。
