#312. 戳气球

有 n 个气球，编号为 0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。如果你戳破气球 i，就可以获得 nums[left] * nums[i] * nums[right] 个硬币。这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。

求所能获得硬币的最大数量。

说明：

  • 你可以假设 nums[-1] = nums[n] = 1，但注意它们不是真实存在的所以并不能被戳破。
  • 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

示例:

1
2
3
4
输入: [3,1,5,8]
输出: 167
解释: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
     coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

#写在前面

没太做出来，想了很久，官方给的思路根本不可能想出来。。。顺着 Burst Balloons（leetcode戳气球，困难）从指数级时间复杂度到多项式级时间复杂度的超详细优化思路（回溯到分治到动态规划） 的思路一点点自己做下来的。

#递归+回溯

最简单的办法就是穷举，把所有可能的情况都列举一次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class BurstBalloonsSolution {
    int c; // 用来统计计算次数

    public int maxCoins(int[] nums) {
        boolean[] flag = new boolean[nums.length];
        this.c = 0;
        int r = burst(nums, flag, 0);
        System.out.println(c);
        return r;
    }

    public int burst(int[] nums, boolean[] flag, int count) {
        int max = 0;
        int n = nums.length;

        if (count == n) // 戳够了足够多的气球之后，就不戳了
            return 0;
        for (int i = 0; i < n; i++) { // 遍历气球数组
            if (!flag[i]) { // 如果当前气球没有被戳过
                flag[i] = true; // 标记当前气球为已戳

                int res = find(nums, flag, i) * nums[i] + burst(nums, flag, count + 1); // 计算戳当前气球能拿到的分数，然后递归剩下的气球
                if (res > max) {
                    max = res; // 更新最大值
                }

                flag[i] = false; // 回溯，把戳过的气球还原
            }
        }
        return max;
    }

    public int find(int[] nums, boolean[] flag, int cur) { // find 方法是找到当前气球的前一个和后一个，相乘并返回
        this.c += 1; // 计数
        int i = cur;
        int pre = 1;
        int next = 1;
        cur -= 1;
        while (cur >= 0) {
            if (!flag[cur]) {
                pre = nums[cur];
                break;
            }
            cur -= 1;
        }
        cur = i + 1;
        while (cur < nums.length) {
            if (!flag[cur]) {
                next = nums[cur];
                break;
            }
            cur += 1;
        }
        return pre * next;
    }
}

运行之后能够得到结果，但是这样的一个程序的时间复杂度达到了 n!，显然不行。

#分治

摸了，先上代码。