戳气球 - Burst Balloon | 个人笔记存档

【DP】【分治】

Problem Link

有 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

Example:

示例:

输入: [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

Solutions

Solution 【DP】【分治】 ( 20ms)

 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


class Solution {
  public int maxCoins(int[] nums) {
    if (nums.length == 0) {
      return 0;
    }
    if (nums.length == 1) {
      return nums[0];
    }
    /* Initial coins[] */
    int length = nums.length + 2;
    int[] coins = new int[length];
    coins[0] = 1;
    for (int i = 1, max_len = length - 1; i < max_len; i++) {
      coins[i] = nums[i - 1];
    }
    coins[length - 1] = 1;
    int[][] dp = new int[length][length];
    /* Initialized */
    int l; // left
    int r; // right
    for (int len = 2; len < length; len++) {
      for (l = 0; l + len < length; l++) {
        r = l + len;
        for (int k = l + 1; k < r; k++) {
          dp[l][r] = Math.max(dp[l][r],
              dp[l][k] + coins[l] * coins[k] * coins[r] + dp[k][r]);
        }
      }
    }
    return dp[0][length - 1];
  }
}

Solution ( 5ms)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution {
    public int maxCoins(int[] nums) {
        int num[] = new int[nums.length+2];
        int res[][] = new int[num.length][num.length];
        num[0] = 1;
        num[nums.length+1] = 1;
        for(int i = 1; i < num.length-1; i++){
            num[i] = nums[i-1];
        }
        return dp(num, 0, num.length-1, res);
    }
    
    public int dp(int[] num, int left, int right, int[][] res){
        if(left == right - 1) return 0;
        if(res[left][right] > 0) return res[left][right];
        int max = 0;
        for(int i = left + 1; i < right; i++){
            max = Math.max(max, num[i] * num[left] * num[right] + 
                           dp(num, left, i, res) + dp(num, i, right, res));
        }
        res[left][right] = max;
        return max;
    }
}

Notes

Reference

戳气球 - Burst Balloon