# 312. Burst Balloons (Hard)

https://leetcode.com/problems/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 `right` then 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:

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

## Solutions

``````public class Solution {

// This problem is complicated, but it is a typical dynamic problem and worth trying.

public int maxCoins(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}

int len = nums.length;

// max coins we can get when burst balloons in window x, y, or nums[x:y], where y is inclusive.
int[][] dp = new int[len][len];

// ws means window side
for (int ws = 1; ws <= len; ws++) {

// work out the max coins for given window size
for (int start = 0; start <= len - ws; start++) {

// ending index of search window
int end = start + ws - 1;

// At this point, we have dp for windows of which sizes are from 1 to ws - 1
for (int i = start; i <= end; i++) {

// Suppose only i left, others in the window all burst. We need to plus the max
// coins of both sides when they burst.

// 1. max coins when burst all balloons in range [start, i-1];
// 2. max coins when burst all balloons in range [i + 1, end];

int coins = nums[i] * getValue(nums, start - 1) * getValue(nums, end + 1);

if (ws != 1) {
// i is the first one, we can only add right side
if (i == start) {
coins += dp[i + 1][end];
}
// i is the last one, we can only add left side
else if (i == end) {
coins += dp[start][i - 1];
}
// i is the middle, we can add both sides
else if (ws >= 3) {
coins += dp[start][i - 1] + dp[i + 1][end];
}
}

// Update the max coins if current schema is superior than previous.
dp[start][end] = Math.max(dp[start][end], coins);
}
}
}

return dp[0][nums.length - 1];
}

private int getValue(int[] nums, int i) {
// Deal with num[-1] and num[num.length]
if (i < 0 || i >= nums.length) {
return 1;
}

return nums[i];
}
}
``````

## Incorrect Solutions

``````class Solution {

// Time exceeds the limit.

// serves as cache to keep the best scores of computed nums
Map<String, Integer> scoreMap = new HashMap<>();

public int maxCoins(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}

List<Integer> numList = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
}

return recurse(numList, numList.size());
}

private int recurse(List<Integer> nums, int len) {
if (nums == null || len == 0) {
return 0;
}

if (len == 1) {
return 1 * nums.get(0) * 1;
}

// if nums already processed, return previous computed score
if (scoreMap.containsKey(nums.toString())) {
return scoreMap.get(nums.toString());
}

// keep the score of the best scheme
int max = 0;

for (int i = 0; i < len; i++) {
// calculate if scores after burst balloon i
int score = 0;

if (i == 0) {
score = 1 * nums.get(0) * nums.get(1);
} else if (i == len - 1) {
score = nums.get(len - 2) * nums.get(len - 1) * 1;
} else {
score = nums.get(i - 1) * nums.get(i) * nums.get(i + 1);
}

// save it for recover purpose
int burstOne = nums.get(i);

// shift elements after i forward by 1 step, simultaneously move element i to the end
nums.remove(i);

score += recurse(nums, len - 1);

max = Math.max(max, score);

// undo above shift process
}

// keep score of nums to cache
scoreMap.put(nums.toString(), max);

return max;
}
}
``````