187 导弹防御系统（最长上升子序列 + dfs）

迷南。 2022-09-11 15:09 106阅读 0赞

**1. 问题描述：**

为了对抗附近恶意国家的威胁，R 国更新了他们的导弹防御系统。一套防御系统的导弹拦截高度要么一直严格单调上升要么一直严格单调下降。例如，一套系统先后拦截了高度为 3 和高度为 4 的两发导弹，那么接下来该系统就只能拦截高度大于 4 的导弹。给定即将袭来的一系列导弹的高度，请你求出至少需要多少套防御系统，就可以将它们全部击落。

**输入格式**

输入包含多组测试用例。对于每个测试用例，第一行包含整数 n，表示来袭导弹数量。第二行包含 n 个不同的整数，表示每个导弹的高度。当输入测试用例 n=0 时，表示输入终止，且该用例无需处理。

**输出格式**

对于每个测试用例，输出一个占据一行的整数，表示所需的防御系统数量。

**数据范围**

1 ≤ n ≤ 50

**输入样例：**

5  
3 5 2 4 1  
0

**输出样例：**

样例解释  
对于给出样例，最少需要两套防御系统。一套击落高度为 3,4 的导弹，另一套击落高度为 5,2,1 的导弹。  
来源：[https://www.acwing.com/problem/content/description/189/][https_www.acwing.com_problem_content_description_189]

**2. 思路分析：**

分析题目可以知道这道题目类似于[拦截导弹][Link 1]的题目，但是又有所不同。拦截导弹那道题目求解的是至少需要多少个不下降的子序列能够将所有的数字覆盖掉，这道题目其实是多了一种选择，求解至少需要多少个上升或者下降的序列能够将所有的数字覆盖掉，多了一种选择之后我们是无法知道怎么样决策是最优的，所以需要通过搜索来解决（**dfs**），主要的策略是对于当前的数字尝试加入到之前上升的子序列或者是下降的子序列的后面，如果不能够添加到之前的序列后面那么就新开一个序列，也即计数加1，我们可以在递归的时候尝试这两种选择，尝试将当前的数字添加到之前的序列后面，在添加数字到之前序列的过程其实与拦截导弹题目的过程是一样的，使用的是贪心的思想。在dfs的方法中我们需要维护几个动态变化的参数，up，down分别记录到当前位置的每一个子序列最后的那个数字，su和sd记录up，down数组的长度，u表示当前递归的位置。主要是理解其中dfs与最长子序列结合的思想。

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        # 使用全局变量进行更新
        res = 0
    
        def dfs(self, up: List[int], down: List[int], h: List[int], u: int, su: int, sd: int):
            # 超过了答案之后说明往下递归不会使得答案更小所以直接返回即可, 当前这个剪枝挺有效的, 因为在求解的时候答案只能越来越小
            if su + sd >= self.res: return
            # 已经到到达了最后一个数字的位置
            if u == len(up):
                self.res = min(self.res, su + sd)
                return
            k = 0
            # 下面其实尝试将当前的数字添加到之前存在的上升子序列或者是下降子序列的后面
            # up列表中的每一个位置保存的是上升子序列的最后一个数字的值, 所以up列表是递减的顺序
            while k < su and up[k] >= h[u]: k += 1
            if k < su:
                t = up[k]
                up[k] = h[u]
                self.dfs(up, down, h, u + 1, su, sd)
                # 回溯, 因为需要尝试将当前的数字添加到下降子序列的后面所以需要回溯一下, 因为之前的已经修改了up中某个位置的值在往下递归的时候尝试其他的情况会影响到后面的求解
                up[k] = t
            else:
                up[k] = h[u]
                # 因为当前添加一个数字不会影响到后面的求解状态所以不用回溯
                self.dfs(up, down, h, u + 1, su + 1, sd)
            # 当前这个数字尝试添加到下降子序列的后面
            k = 0
            while k < sd and down[k] <= h[u]: k += 1
            if k < sd:
                t = down[k]
                down[k] = h[u]
                self.dfs(up, down, h, u + 1, su, sd)
                down[k] = t
            else:
                down[k] = h[u]
                self.dfs(up, down, h, u + 1, su, sd + 1)
    
        def process(self):
            while True:
                n = int(input())
                if n == 0: break
                h = list(map(int, input().split()))
                up, down = [0] * n, [0] * n    
                # 每一个子序列为一个新的序列所以总共的数量为n
                self.res = n
                self.dfs(up, down, h, 0, 0, 0)
                print(self.res)
    
    
    if __name__ == "__main__":
        Solution().process()

[https_www.acwing.com_problem_content_description_189]: https://www.acwing.com/problem/content/description/189/
[Link 1]: https://blog.csdn.net/qq_39445165/article/details/120343323