312. Burst Balloons(打气球的最大分数)

发表于 | 分类于 | 浏览 次

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 rightthen becomes adjacent.

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

Note:

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

Example:

1
2
3
4
Input: [3,1,5,8]
Output: 167 
Explanation: 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

暴力搜索

第一步是最难的，需要确定暴力搜索的方法，保证能够搜索到所有可能的路径，通过比较所有可能的路径得到最优解。
之后，对暴力搜索进行优化，变成自顶向下的记忆化搜索，再变成自底向上，最后压缩空间。

自顶向下

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
class Solution {
public:
    int maxCoins(vector<int>& nums) {
        if(nums.empty()){
            return 0;
        }else if(nums.size() == 1){
            return nums[0];
        }
        int n = nums.size();
        vector<int> help(n + 2, 1);
        for(int i=0;i<n;i++){
            help[i+1] = nums[i];
        }
        vector<vector<int>> ans(n+2, vector<int>(n+2, -1));
        int max_score = process(help, 1, n, ans);
        return max_score;
    }
    int process(vector<int>& nums,int lo, int hi, vector<vector<int>> &ans){
        if(ans[lo][hi]!=-1){
            return ans[lo][hi];
        }
        if(lo == hi){
            return nums[lo - 1] * nums[lo] * nums[hi + 1];
        }
        int max_score = max(nums[lo - 1] * nums[lo] * nums[hi + 1] + process(nums, lo + 1, hi, ans), 
                            nums[lo - 1] * nums[hi] * nums[hi + 1] + process(nums, lo, hi - 1, ans));
        
        // 尝试每一个气球最后被打爆的方案
        for(int i = lo + 1;i< hi;i++){
            max_score = max(max_score, nums[lo - 1] * nums[i] * nums[hi + 1] 
                            + process(nums, lo, i - 1, ans) + process(nums, i + 1, hi, ans));
        }
        ans[lo][hi] = max_score;
        return max_score;
    }
};

AC代码2

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
class Solution {
public:
    int maxCoins(vector<int>& nums) {
        if(nums.empty()){
            return 0;
        }else if(nums.size() == 1){
            return nums[0];
        }
        int n = nums.size();
        vector<int> help(n + 2, 1);
        for(int i=0;i<n;i++){
            help[i+1] = nums[i];
        }
        vector<vector<int>> ans(n+2, vector<int>(n+2, -1));
        int max_score = process(help, 1, n, ans);
        return max_score;
    }
    int process(vector<int>& nums,int lo, int hi, vector<vector<int>> &ans){
        if(ans[lo][hi]!=-1){
            return ans[lo][hi];
        }
        if(lo == hi){
            return nums[lo - 1] * nums[lo] * nums[hi + 1];
        }
        
        // max_score初值设置为0，隐含了当lo > hi时，即没有气球可打时，返回0
        int max_score = 0; 
        
        // 尝试每一个气球最后被打爆的方案
        for(int i = lo;i<= hi;i++){
            max_score = max(max_score, nums[lo - 1] * nums[i] * nums[hi + 1] 
                            + process(nums, lo, i - 1, ans) + process(nums, i + 1, hi, ans));
        }
        ans[lo][hi] = max_score; 
        return max_score;
    }
};

自底向上

由解法2可得递推公式：
$$
f[i][j] = \max \limits_{i <= k <= j}{help[i-1]* help[k]*help[j+1] + f[i][k-1] + f[k+1][j]}
$$
另外，初值如下：
$$
f[i][i-1] = 0
$$

$$
1<=i<=n, 1<=j<=n
$$

其中，n为原数组nums的大小。但是这里的help是在原数组nums的最前面和最后面分别加上一个1形成的辅助数组。例如nums= [3,1,5,8]，则help = [1, 3,1,5,8, 1] ，n = 4。

分析填表顺序

压缩空间

1
2