# 戳气球 - Burst Balloon

【DP】 【分治】

`n` 个气球，编号为`0``n-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)

 `````` 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 `````` ``````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 25 `````` ``````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