#yyds干货盘点# 动态规划专题：拦截导弹

1.简述：

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是不大于1000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

数据范围：导弹个数 n 满足  ，导弹的高度 m 满足 

第一行输入一个正整数 n ，表示导弹的个数

第二行输入 n 个正整数，表示导弹的高度

输出一套拦截系统最多拦截多少导弹和最少要配备多少套导弹拦截系统两个正整数

输入：

8
389 207 155 300 299 170 158 65

输出：

6
2

2.代码实现：

import java.util.*;

public class Main {
    static int n;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i < n; i ++)
            nums[i] = in.nextInt();

        System.out.println(func1(nums));
        System.out.println(func2(nums));
    }

    // 最多拦截多少个导弹，线性dp
    public static int func1(int[] nums) {
        int n = nums.length;
        int[] f = new int[n + 1];

        for(int i = 1; i <= n; i ++) {
            f[i] = 1;
            for(int j = 1; j < i; j ++) {
                // 高度相等，两颗导弹均可被拦截
                if(nums[i - 1] <= nums[j - 1]){
                    f[i] = Math.max(f[i], f[j] + 1);
                }
            }
        }

        int ans = 0;
        for(int i = 0; i <= n; i ++)
            ans = Math.max(ans, f[i]);

        return ans;
    }

    // 最少要多少个系统
    public static int func2(int[] nums) {
        int n = nums.length;
        int[] f = new int[n + 1];

        for(int i = 1; i <= n; i ++) {
            f[i] = 1;
            for(int j = 1; j < i; j ++) {
                // 严格递增，高度相等的可以被拦截，因此算为一个系统
                if(nums[i - 1] > nums[j - 1]){
                    f[i] = Math.max(f[i], f[j] + 1);
                }
            }
        }

        int ans = 0;
        for(int i = 0; i <= n; i ++)
            ans = Math.max(ans, f[i]);

        return ans;
    }
}