这是一道动态规划题，和昨天的取硬币还有最长公共字串有点类似。
1.题目描述:
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高 度。某 天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式一行，为导弹依次飞来的高度。
输出格式两行，分别是最多能拦截的导弹数与要拦截所有导弹最少要配备的系统数。
2.样例输入
300 207 155 300 299 170 158 65
3.样例输出
6
2
4.算法思想:
我们遇到这道题目，我们自己算的话就是，先从300开始，然后比较207比300小能拦截，155比207小能拦截，65比155小能拦截，这一趟是能拦截4 个导弹。然后暴力求出每次最多能拦截的导弹数，再比较最大的，这是我们平时的暴力破解思维。但是，这样想想要多少次循环，也太麻烦了。当然最后最多能拦截的是300 300 299 170 158 65这六种。我们应该想到动态规划，动态规划只是一种工具。这道题目怎么用到动态规划呢?动态规划其实就是填矩阵，之前在别的博客上看到求最长子序列的时候填的是二维数组，当然这题也一样是。怎么填呢?在求最长公共子串时从头开始遍历，如果想等，则加1，不等则继续是这个，这道题目呢如下，动态规划要从底部开始动态规划。
300 207 155 300 288 299 170 158 65
6 4 2 5 4 4 3 2 1
刚开始一直没有思路，但是仔细想一下，发现我300比207大，最大序列加一，207比155大加1，但是300不比155大，这时候怎么办，就要递归遍历。但是我从末尾看，只要65是1个长度，只要158大于65，那么158肯定是第二个长度，170大于158，是第3个长度，299大于170，第4个长度，但是288没有299大，前面比较，比170大，所以等于170的长度+1。300比299大，所以长度等于299的长度+1,155比65大，所以155等于65的长度+1,这就得到了状态转移方程。动态规划问题，不管是不是上升序列，都要进行判断，这道题呢是怎么判断的？这个导弹和之前的导弹比较，如果这个导弹比大于之前的并且它的temp值也是最大的，保存这个下标，然后让temp[k] = temp[z] + 1，即得到了最后的结果，所以一定要搞清楚动态规划转移方程。
具体代码示例
package 蓝桥杯;
/*
*
300 207 155 165 288 299 170 158 65
5 4 2 3 4 4 3 2 1
*/
public class 导弹问题 {
static int weizhi[] = {500,700,300,207,155,165,288,299,170,158,65};
public static void main(String[] args) {
//记录最大的位置
int temp[] = new int[weizhi.length];
temp[weizhi.length-1] = 1;
f(temp,weizhi.length-2); //从第7个位置开始
for(int i=0;i<weizhi.length;i++) {
System.out.println(temp[i]);
}
}
private static void f(int[] temp, int k) {
if(k==-1) {
return;
}
int max=0;
int z = 0;
for(int i=k+1;i<=weizhi.length-1;i++) {
if(weizhi[i]<weizhi[k]) {
if(temp[i]>max) {
max = temp[i];
z = i;
}
}
temp[k] = temp[z]+1;
f(temp, k-1);
}
}
}