铭记各位大佬教导，开始看一些很迷的动态规划，那就从比较典型的01背包开始吧，想想还是从比较简单的导弹拦截开始吧，说简单都是骗人的，还是看采药吧。
一、动态规划
刚听到动态规划这个东西，据HLT大佬所言，就是类似于数列的递推公式，将每一步的最佳情况叠加到一起，在所谓体积与价值之间取一个最优解，综合考虑，颇像二次函数最大值的情况。然而想让每一种问题直接慢慢搜索，慢慢磨到最大值，对于一些很gay的值，是不能接受的，所以才有了将一个大工程分成多个子工程，每一个小工程都有一个最优解，在每一个最优解上构造整体最优解，像是，恩，一个大楼， 从第一层开始建，建第二层时考虑第一层的顶齐不齐，底稳不稳，第三层时看第二层，然而在建第三层时不会影响到第四层的建设情况（每一层都达到最优的情况时）就像是需要一个76楼的大厦，前面的75层都是最优解，符合他的下面一层的结构，很稳定，那么最后封顶之后，这个就是整体最优解了。（是这个理吧，很尬的是我也不是很清楚）
在建好每一层之后，不会对下一层的建设造成任何的影响，那么就是无后效性了。无后效性就是，某阶段的状态一旦确定，这个阶段以后的过程演变就和这个阶段以前的状态和决策无关了，只和这个阶段的状态有关，当前状态是此前历史的完整总结，此前的状态和决策只能通过当前状态去影响过程未来的演变。有的文章则认为，无后效性就是未来的状态和决策不会影响以前的状态、决策和目标。以前发生过的事就是板上钉钉的事，不会更改。就像是一条直线，前面的每一步都走得正确，就不会对后面的造成影响，不会让这个最后产生的值影响到最开始的值（最后最高的这一层大楼对第一层产生影响）他的状态的确定，只受其前面的一个值的影响，（数列的递推公式），而不是一个环。
所以动态规划就有了一个叫状态转移方程的东西。其核心观点就是前一状态的改变影响并且确定影响该状态的改变，有一个状态转移方程x( k+1 ) = T k( x(k),u(k) ) //u(k)为决策，即下一阶段K+1的状态X受k阶段的状态x和k阶段的决策u共同构成的上一阶段的状态的影响，而所谓的T就是一个常数？表示其受影响程度。
所以动态规划与分治法的区别也就因此而体现，动态规划在分解成每一个子程序后，每个子程序，每一个状态都跟其他的有关，而不是像分治法一样完全独立。
然而动态规划需要保存每一个最优解，其空间所占量也是非常的影响，对于一个子问题，会有重复性计算，免除冗杂计算就可以优化DP了，虽然所占的空间很大，然而对于时间而言是很少的，所以像是一种空间换时间的一种算法。
那么看了很久，发现DP又分很多类，有线性DP，区域DP，树形DP，背包DP四类。
线性DP：拦截导弹，合唱队形，挖地雷，建学校，剑客决斗等；
区域DP：石子合并， 加分二叉树，统计单词个数，炮兵布阵等；
树形DP：贪吃的九头龙，二分查找树，聚会的欢乐，数字三角形等；
背包DP：01背包问题，完全背包问题，分组背包问题，二维背包，装箱问题等；
既然很多问题都已经理解了差不多了，那么就可以拿来看第一题了，先从拦截导弹开始
拦截导弹 时间限制： ms | 内存限制： KB 难度： 描述 某国为了防御敌国的导弹袭击，发展中一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于等于前一发的高度。某天，雷达捕捉到敌国导弹来袭。由于该系统还在试用阶段，所以只用一套系统，因此有可能不能拦截所有的导弹。 输入 第一行输入测试数据组数N（<=N<=） 接下来一行输入这组测试数据共有多少个导弹m（<=m<=） 接下来行输入导弹依次飞来的高度，所有高度值均是大于0的正整数。 输出 输出最多能拦截的导弹数目 样例输入 样例输出
题目
#include<stdio.h>
#include<string.h>
],a[];
int main()
{
int t,n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
memset(dp,,sizeof(dp));
int max,max2;
;i<n;i++)
scanf("%d",&a[i]);
max2=;
dp[]=;
;i<n;i++)//默认从第二位开始，dp[0]已经等于1
{
max=;
;j<=i-;j++)
{
>max)//当前导弹的高度不能高于前边的导弹
max=dp[j]+;//记录最大拦截数
}
dp[i]=max;//i与它之前的数组合，所能组成的最长的递减序列长度
if(max2<max) max2=max;//max2来记录dp中的最大数，也就是最大拦截数
}
printf("%d\n",max2);
}
;
}
题解
看着不是很长，只是一个多重循环的题，然而其核心代码
max2=;
dp[]=; //作为标志变量？
;i<n;i++)//默认从第二位开始，dp[0]已经等于1
{
max=;
;j<=i-;j++)
{
>max)//当前导弹的高度不能高于前边的导弹
max=dp[j]+;//记录最大拦截数
}
dp[i]=max;//i与它之前的数组合，所能组成的最长的递减序列长度
if(max2<max) max2=max;//max2来记录dp中的最大数，也就是最大拦截数
}
有大佬来讲了一波，这种是最长下降子序列，和导弹高度逐渐变低感觉是一样的，求其能拦截的最长序列，于是回归背包问题，采药。//这个先颓着不着急。
/*莫名想着先断更，因为没有学函数，找遍全网发现需要了解的东西太多
一、动态规划转移方程。 （√）
二、有无后效性对动态规划的影响。
三、所谓局部最优解，代码实现长什么样。
四、贪心与DP的区别。
五、因为没有学过函数，所以无法理解很多代码。 （√）
六、DP的状态改变。 （√）
七、递推递归的深入理解。（√）
那么这个先断着，之后有了更加深入的学习和理解之后再写吧。*/
0323更：本来以为可以解决这些问题了，但是走了一遍调试还是有点蒙，以及递归的返回的情况有些懵比，void不是很会用，但是即便是这样， 还是放一道DP题，欢乐世界杯
那是我愿意付诸一生的人，现在却没法拥有。