You've successfully subscribed to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your billing info is updated.
Billing info update failed.

# 312. 戳气球 - Burst Balloon

【DP】 【分治】

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

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

### Example:

输入: [3,1,5,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;
}
}


Reference