Comment on page

# 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

## Analysis

A very nice analysis on LeetCode talking about several approaches from brute-force to divide and conquer as well as dynamic programming:

### Divide and Conquer with Memoization

subproblems are overlapped, so we can use divide and conquer + cache
• Balloons `0, 1, ..., n - 1`
• What is the max value if we burst all of them`[0, n - 1]`?
• Let's first consider bursting`[start, end]` (including `start` and `end` boundaries)
• Imagine index `i` as the last one in the interval to be bursted
• `[start, ... i - 1, (i), i + 1 ... end]`
• Before the end, we already bursted `[start, i - 1]` and `[i + 1, end]`
• Before the end, boundaries `start - 1` , `i` , `end + 1` are always there
• This helps us calculate coins without worrying about details inside`[start, i - 1]` and `[i + 1, end]`
• So the range can be divided into `start - 1` ,`maxCoin(start, i - 1)`, `i`, `maxCoins(i + 1, end)`, `end + 1`

### Dynamic Programming

State:
• `dp[i][j]`表示 i 到 j 区间中，打爆所有气球的最大coin数目
Function:
• 对于所有k属于`{i,j}`, 表示第k号气球最后打爆。`k` is the last balloon to burst.
• `midValue = arr[i- 1] * arr[k] * arr[j + 1];`
• `dp[i][j] = max(dp[i][k-1] + d[k+1][j] + midvalue)`
Initialize:
• for each `i`
• `dp[i][i] = 0`
• `dp[0][n-1]`

## Solution

Divide & Conquer + Recursive + Memoization - Easy to Understand Solution (16 ms, faster than 14.04%)
`start`, `end` boundary included (boundaries will be burst)
`[start, ... i - 1, (i), i + 1 ... end]`
class Solution {
public int maxCoins(int[] nums) {
int[][] dp = new int[nums.length][nums.length];
return maxCoinsHelper(nums, 0, nums.length - 1, dp);
}
public int maxCoinsHelper(int[] nums, int start, int end, int[][] dp) {
if (start > end) return 0;
if (dp[start][end] != 0) return dp[start][end];
int max = 0;
for (int i = start; i <= end; i++) {
int val = maxCoinsHelper(nums, start, i - 1, dp) +
maxCoinsHelper(nums, i + 1, end, dp) +
getVal(nums, start - 1) * getVal(nums, i) * getVal(nums, end + 1);
max = Math.max(max, val);
}
dp[start][end] = max;
return max;
}
private int getVal(int[] nums, int i) {
if (i == -1 || i == nums.length) {
return 1;
}
return nums[i];
}
}
*(Favorite) - Same idea as above (Divide & Conquer with Memoization) but faster performance (6ms 87.86%)
Building a new array first for faster access, compared to above `getVal()` function
public class Solution {
public int maxCoins(int[] nums) {
if(nums == null || nums.length == 0) return 0;
int n = nums.length;
int[] arr = new int[n + 2];
arr[0] = 1;
arr[n + 1] = 1;
for(int i = 0; i < n; i++){
arr[i + 1] = nums[i];
}
int[][] dp = new int[n + 2][n + 2];
return memoizedSearch(1, n, arr, dp);
}
private int memoizedSearch(int start, int end, int[] arr, int[][] dp){
if(dp[start][end] != 0) return dp[start][end];
int max = 0;
for(int i = start; i <= end; i++){
int cur = arr[start - 1] * arr[i] * arr[end + 1];
int left = memoizedSearch(start, i - 1, arr, dp);
int right = memoizedSearch(i + 1, end, arr, dp);
max = Math.max(max, cur + left + right);
}
dp[start][end] = max;
return max;
}
}
*Divide and Conquer, Memoization, Recursive - (Runtime: 5 ms, faster than 99.18%)
(not including boundaries in the recursion - boundary balloons not bursted)
class Solution {
public int maxCoins(int[] iNums) {
int[] nums = new int[iNums.length + 2];
int n = 1;
for (int x : iNums) if (x > 0) nums[n++] = x;
nums[0] = nums[n++] = 1;
int[][] memo = new int[n][n];
return burst(memo, nums, 0, n - 1);
}
public int burst(int[][] memo, int[] nums, int left, int right) {
if (left + 1 == right) return 0;
if (memo[left][right] > 0) return memo[left][right];
int ans = 0;
for (int i = left + 1; i < right; ++i)
ans = Math.max(ans, nums[left] * nums[i] * nums[right]
+ burst(memo, nums, left, i) + burst(memo, nums, i, right));
memo[left][right] = ans;
return ans;
}
}
Dynamic Programming - 6 ms , faster than 88.28%
public int maxCoins(int[] iNums) {
int[] nums = new int[iNums.length + 2];
int n = 1;
for (int x : iNums) if (x > 0) nums[n++] = x;
nums[0] = nums[n++] = 1;
int[][] dp = new int[n][n];
for (int k = 2; k < n; ++k)
for (int left = 0; left < n - k; ++left) {
int right = left + k;
for (int i = left + 1; i < right; ++i)
dp[left][right] = Math.max(dp[left][right],
nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right]);
}
return dp[0][n - 1];
}