文档介绍：章
动态规划
最优化原理
1951年美国数学家R,Bellman等人，根据一类多阶段问题的特点，把多阶段决策问题 变换为一系列互相联系的单阶段问题，然后逐个加以解决。一些静态模型，只地定义最优值；
（3） 采用自底向上的方式计算问题的最优值；
（4 ）根据计算最优值时得到的信息，构造最优解。
1〜3步是动态规划算法解决问题的基本步骤，在只需要计算最优值的问题中，完 成这三个基本步骤就可以了。如果问题需要构造最优解，还要执行第 4步；此时，在
第3步通常需要记录更多的信息，以便在步骤 4中，有足够的信息快速地构造出最优 解。
〖案例1〗拦截导弹
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有 一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前 一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一 套系统，因此有可能不能拦截所有的导弹。
输入数据为导弹依次飞来的高度，所有高度值均为不大于30000的正整数。
输出只有一行是这套系统最多能拦截的导弹数。
389 207 155 300 299 170 158 65
因为只有一套导弹拦截系统，并且这套系统除了第一发炮弹能到达任意高度外，以后 的每一发炮弹都不能高于前一发炮弹的高度；所以，被拦截的导弹应该按飞来的高度组成 一个非递增序列。题目要求我们计算这套系统最多能拦截的导弹数，并依次输出被拦截导 弹的高度，实际上就是要求我们在导弹依次飞来的高度序列中寻找一个最长非递增子序列。
设X={x「x2,…,xn}为依次飞来的导弹序列，Y={y「y2,…,yk}为问题的最优解（即X的最 长非递增子序列），S为问题的状态（表示导弹拦截系统当前发送炮弹能够到达的最大高 度，初值为s=8—第一发炮弹能够到达任意的高度）。如果yi=xi，即飞来的第一枚导 弹被成功拦截。那么，根据题意“每一发炮弹都不能高于前一发的高度”，问题的状态将 由s=8变成s<x1 （x1为第一枚导弹的高度）；在当前状态下，序列Y]={y2，…,yk}也应该 是序列X]={x2,…,xn}的最长非递增子序列（大家用反证法很容易证明）。也就是说，在当 前状态s<x1下，|、问题的最优解Y所包含的子问题（序列X1）的解（序列Yp也是最优的。 这就是拦截导弹问题的最优子结构性质。
设D（i）为第i枚导弹被拦截之后，这套系统最多还能拦截的导弹数（包含被拦截的第i 枚）。我们可以设想，当系统拦截了第k枚导弹xk，而xk又是序列X={x1,x2,„,xn}中的最 小值，即第k枚导弹为所有飞来的导弹中高度最低的，则有D（k）=1 ；当系统拦截了最后一 枚导弹xn，那么，系统最多也只能拦截这一枚导弹了，即D（n）=1；其它情况下，也应该有 D（i） 31「根据以上分析，可归纳出问题的动态规划递归方程为：
max {D(j) +1) 3 < n
湖』3 <j <=n'
假设系统最多能拦截的导弹数为dmax （即问题的最优值），则
dmax = ]翳{口3} （i为被系统拦截的第一枚导弹的顺序号）
所以，要计算问题的最优值dmax，需要分别计算出D（1）、D（2）、……D（n）的值， 然后将它们进行比较，找出其中的最大值。根据上面分析出来的递归方程，我们完全可以 设计一个递归函数，采用自顶向下的方法计算D（i）的值。然后，对i从1到n分别调用 这个递归函数，就可以计算出D（1）、D（2）、……D（n）。但这样将会有大量的子问题被 重复计算。比如在调用递归函数计算D（1）的时候，可能需要先计算D（5）的值；之后 在分别调用递归函数计算D（2）、D（3）、D（4）的时候，都有可能需要先计算D（5）的 值。如此一来，在整个问题的求解过程中，D（5）可能会被重复计算很多次，从而造成了 冗余，降低了程序的效率。
其实，通过以上分析，我们已经知道：D（n）=1。如果将n作为阶段对问题进行 划分，根据问题的动态规划递归方程，我们可以采用自底向上的方法依次计算出 D
（n-1）、D（n-2）、……D（ 1）的值。这样，每个 D（i）的值只计算一次，并在计算 的同时把计算结果保存下来，从而避免了有些子问题被重复计算的情况发生，提高了 程序的效率。
int main () {
int h[2000],d[2000],count,c;//h表示高度值，d表示最优值，c是能拦截得最多导弹数 count=0;
while ( scanf ( "%d",h+count++ ) !=EOF ) ; //输入高度
d[0]=h[0];
c=1;
for ( i = 1;i<cou