You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

312. 戳气球 - Burst Balloon

. 2 min read

【DP】 【分治】

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

现在要求你戳破所有的气球。每当你戳破一个气球 i 时,你可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 leftright 代表和 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)

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)

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