java动态规划导弹问题

这是一道动态规划题，和昨天的取硬币还有最长公共字串有点类似。
　
1.题目描述:

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式一行，为导弹依次飞来的高度。

输出格式两行，分别是最多能拦截的导弹数与要拦截所有导弹最少要配备的系统数。

2.样例输入

300 207 155 300 299 170 158 65

3.样例输出
6

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);

		}

	}

}

巴特西

java动态规划导弹问题

最新文章

热门文章