leetcode312.Burst Balloons

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note: 
(1) You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
(2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Given [3, 1, 5, 8]

Return 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

这里讲了一个炸气球小游戏的规则。当我们选中一个气球并炸掉它后，会得到该气球以及其相邻两个气球的分数的乘积，并加入我们的积分。
之后该气球将消失，从而其左右两个气球成为相邻的气球。问如何选择气球才能使得积分数最高。

思路和代码

我直接解释一下看到的最高票的回答。

如果采用暴力法的话，我们会遍历出所有可能的结果，并且比较其最终获得最高积分值。这意味着O(n!)的时间复杂度。

如果采用动态规划法的话，我们在知道了炸掉k个气球之后的最大积分，然后计算炸掉k+1个气球的最大积分。时间依旧感人。

这里采用的是backtracking+分治法来解决。当我们正向思考这道题时，我们可能会想，随机选择一个气球，按该气球作为分界线分为两个子气球队列。这时再分别计算左右两个队列可以得到的最大积分。
但是这里有一个问题在于，左边队列炸掉气球的顺序可能会影响到右边气球的顺序，比如假设存在这样一列气球对应的积分为3，2，4，1，5,我们取4作为分界点，分为两个子数组3,2,1,5那么如果左边气球炸掉的顺序为2,3，则右边队列的最左侧值则会先是2，再是3。这样就违背了分治法将问题分解为独立问题的要求。因此这种思路无法解决该问题。

但是如果反过来思考，假设我们先选取最后一个炸掉的气球，那么我们知道这个获得的积分一定是nums[i]*nums[left]*nums[right]，则以该气球作为分界点将队列分解后获得的两个子队列的边界是一定的。举个例子3,2,4,1,5：
首先，我们将其填充为1,3,2,4,1,5,1
然后我们将队列从2分解开来，即2是最后一个炸掉的气球，那么该气球的积分数为1*2*1
自队列分别为1,3,2和2,4,1,5,1。
那么假设我们再拆解1,3,2中的3，则结果为1*3*2。此时得到的子队列长度等于2，因此将无法拆解，即结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int maxCoins(int[] nums) {
    int[] modifiedNums = new int[nums.length + 2];
    int n = 1;
    for(int num : nums){modifiedNums[n++] = num;}
    modifiedNums[0] = modifiedNums[n++] = 1;
    
    int[][] memo = new int[n][n];
    return maxCoins(modifiedNums, 0, n-1, memo);
}

public int maxCoins(int[] nums, int left, int right, int[][] memo){
    if(left+1 >=right) return 0;
    if(memo[left][right] != 0) return memo[left][right];
    int res = 0;
    for(int i = left+1; i<right ; i++){
        res = Math.max(res, nums[i]*nums[left]*nums[right] +  maxCoins(nums, left, i, memo)  + maxCoins(nums, i, right, memo));
    }
    memo[left][right] = res;
    return res;
}