题目链接：题目链接
题面：
小王在开完飞机后还是觉得不过瘾，认为会开飞机并不值得吹捧，如果能将对手的飞机摧毁才是真的本事！
小张看到小王无法按捺住激动的心灵，于是给他的飞机安装了一个 “无限导弹发射器”。
小王只要瞄准了某架飞机，每按下一次发射键，就可以扣除飞机的一点生命值，一心一意的小王只要开始打了某架飞机，就会把这架飞机彻底摧毁，且摧毁之前不会再打其他飞机。
太空飞机场是一个神奇的地方，当第 i 架飞机被摧毁时，剩余飞机（被摧毁的除外）会自动变更其生命值，其中第 j 架飞机变更为 map[i][j]，这课打乱了小王的射击节奏。
小王为了展示自己的发射能力，计划先打生命值低的飞机，再逐步打击生命值高的飞机，即后打击飞机的生命值必定大于等于前打击飞机的生命值。
小王必须从第一架飞机开始（第一架飞机生命值固定为 0），请问小王最多可以击毁多少架飞机？
知识点
- 穷举
- 搜索
- Java 函数语法
初始代码
/** * @param map 二维数组，可通过 map.get("i,j") 取值 * @param n 二维数组的长度（X 坐标长度和 Y 坐标长度一致） * @return 最多可以击毁的飞机数 */ public static Long doWork(HashMap<String,Integer> map,int n) { //代码编辑区 开始 //代码编辑区 结束 return 0L; } public static void main(String[] args) { //测试用例 System.out.println((Objects.equals(2L,doWork(initHashMap1(),3)) ? "【√正确】" : "【X错误】 ") + "样例一，答案：" + doWork(initHashMap1(),3)); System.out.println((Objects.equals(4L,doWork(initHashMap2(),4)) ? "【√正确】" : "【X错误】 ") + "样例二，答案：" + doWork(initHashMap2(),4)); }
样例说明
输入数据是一个哈希 Map，内置了一个二维数组，同学们可以通过 i,j 键获取 map[i][j] 的数据。
map[i][j] 的数值代表击毁第 i 架飞机后，第 j 架飞机变更后的生命值上限，其中 map[i][i] 固定为 0，因为第 i 架飞机被摧毁后，再设置大于 0 的生命值没有意义。
同学们可以认为小王是从击毁第 1 架飞机后开始的，第 1 架飞机的生命值固定为 0。
题目需要输出一个数 X，X是小王采取后打击飞机的生命值必定大于等于前打击飞机的生命值的计划，最多可击毁的飞机数量。
样例一：
0 7 8 1 0 2 3 6 0
小王打掉第一架飞机后，剩余飞机的情况为：X 7 8（X代表已被摧毁）。
接着根据先易后难的思路，先打第二架，剩余飞机情况为：X X 2，其中 2 取值为数组 map[2][3],即摧毁第二架飞机后，第三架飞机变更的生命值。
因为第三架飞机的生命值 2 小于 上一架摧毁的 7，所以不能再摧毁，所以答案为 2。
样例二：
0 4 1 6 0 0 7 7 3 5 0 7 3 6 1 0
小王打掉第一架飞机后，剩余飞机的情况为：X 4 1 6。
接着摧毁第三架飞机，剩余飞机的情况为：X 5 X 7，其中 5 来自 map[3][2]，7 来自 map[3][4]。即摧毁第 i 架飞机后 第 j 架飞机的生命值。
接着摧毁第二架飞机，剩余飞机的情况为：X X X 7，其中 7 来自 map[2][4]。
最后摧毁第四架飞机，全部飞机被摧毁，所以答案为 4。
提示：这里只讲了最优解的情况，即演示从初始数据得到答案的过程，飞机摧毁顺序需要你自己做判断！
题解
考察对基本搜索的理解，首先小张解决了生命值为 0 的飞机，接下来要找第 1 辆飞机到第 N 辆没被摧毁的飞机中生命值高于前者的飞机。
很明显我们可以用深搜去解决，只搜索没被摧毁的飞机中生命值高于前者的飞机，搜索成功后则更新积分，若更新后积分大于全局积分则更新全局积分。
待全部情况都搜索完成后，全局积分必定是最高积分。
参考代码如下：
import java.util.*; public class IAns { private final static Boolean[] flag = new Boolean[20]; private static Long sum = 0L; /** * @param map 二维数组，可通过 map.get("i,j") 取值 * @param n 二维数组的长度（X 坐标长度和 Y 坐标长度一致） * @return 最多可以击毁的飞机数 */ public static Long doWork(HashMap<String,Integer> map,int n) { sum = 0L; for(int i = 0; i < 20; i ++) { flag[i] = false; } flag[1] = true; dfs(1, 1L, -1,map,n); return sum; } private static void dfs(int x,Long ans,int maxx,HashMap<String,Integer> map,int n) { if (ans > sum) { sum = ans; } for (int i = 1; i <= n; i++) { if (i == x) { continue; } if (map.get(x + "," + i) >= maxx && !flag[i]) { flag[i] = true; dfs(i, ans + 1, map.get(x + "," + i),map,n); flag[i] = false; } } } public static void main(String[] args) { //测试用例 System.out.println((Objects.equals(2L,doWork(initHashMap1(),3)) ? "【√正确】" : "【X错误】 ") + "样例一，答案：" + doWork(initHashMap1(),3)); System.out.println((Objects.equals(4L,doWork(initHashMap2(),4)) ? "【√正确】" : "【X错误】 ") + "样例二，答案：" + doWork(initHashMap2(),4)); } private static HashMap<String,Integer> initHashMap1() { HashMap<String,Integer> ans = new HashMap<>(); ans.put("1,1",0); ans.put("1,2",7); ans.put("1,3",8); ans.put("2,1",1); ans.put("2,2",0); ans.put("2,3",2); ans.put("3,1",3); ans.put("3,2",6); ans.put("3,3",0); return ans; } private static HashMap<String,Integer> initHashMap2() { HashMap<String,Integer> ans = new HashMap<>(); ans.put("1,1",0); ans.put("1,2",4); ans.put("1,3",1); ans.put("1,4",6); ans.put("2,1",0); ans.put("2,2",0); ans.put("2,3",7); ans.put("2,4",7); ans.put("3,1",3); ans.put("3,2",5); ans.put("3,3",0); ans.put("3,4",7); ans.put("4,1",3); ans.put("4,2",6); ans.put("4,3",1); ans.put("4,4",0); return ans; } }
总结
要 AC 本题，必须学会穷举和搜索的算法，使用 DFS，只搜索没被摧毁的飞机中生命值高于前者的飞机，不断更新全局积分，最终通过本题。
