## 312. 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
``````

Thoughts:

1. dp[left][right]: ... from subarray[left ... right]
2. recursive function: dp[left][right] = max(..., dp[left][i], nums[left] * nums[i] * nums[right] + dp[i][right])
3. propagating direction: from small sliding window to larger sliding window
4. return dp[0][n-1] (from left = 0 to right n-1)

Code T: O(n^3) & S: O(n^2)

``````class Solution {
public int maxCoins(int[] nums) {
// first busing 0s
int [] nums_pad = new int [nums.length + 2];
int n = 1;
for (int x : nums) if( x > 0) nums_pad[n++] = x;

int [][] dp = new int [n][n];
for(int s = 2; s < n; s++){ // s is the length of the sliding window
for(int left = 0 ; left + s < n; left++){
int right = left + s;
for(int i = left + 1; i < right; i++){
dp[left][right] = Math.max(dp[left][right],
);
}
}
}

return dp[0][n-1];
}
}
``````
``````class Solution {
public:
int maxCoins(vector<int>& nums) {
// first bursting 0s
int n = 1;
for (int x : nums) if( x > 0) nums_pad[n++] = x;

int dp[n][n]  = {};
for(int s = 2; s < n; s++){
for(int left = 0 ; left + s < n; left++){
int right = left + s;
for(int i = left + 1; i < right; i++){
dp[left][right] = max(dp[left][right],
);
}
}
}

return dp[0][n-1];
}
};
``````
``````class Solution(object):
def maxCoins(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums_pad = [1] + [x for x in nums if x > 0] + [1]
dp = [[0]* n for _ in range(n)] # a fancy way of building the nxn matrix filled with 0

for s in range(2,n):
for left in range(0, n - s):
right = left + s
for i in range(left + 1, right):

return dp[0][n-1]
``````

A Divide & Conquer solution

``````class Solution {
public int maxCoins(int[] nums) {
// first busing 0s
int [] nums_pad = new int [nums.length + 2];
int n = 1;
for (int x : nums) if(x > 0) nums_pad[n++] = x;

int [][] mem = new int [n][n]; // memoization step
return burstBallon(mem, nums_pad, 0 , n -1);
}

public int burstBallon(int[][] mem, int [] nums, int left, int right){
// top down + bottom up fashion

// base case
if (left == right -1) return 0;
if (mem[left][right] > 0) return mem[left][right];
int ans = 0;

// caculation step
for(int i = left + 1; i < right; i++){
ans = Math.max(ans, nums[left] * nums[i] * nums[right] + burstBallon(mem,nums, left, i) +  burstBallon(mem,nums, i, right));
}
mem[left][right] = ans; //memoization step

return ans;
}
}
``````

Note: In this case the reason why recursive solution with memoization is faster is because for some DP problems, we might not have to examine "all" the sub-problems, which most of the bottom-up table building iterative solutions do. In those cases, recursive solution examine less sub-problems, and that compensate for the overhead from recursion.

However, iterative solution is definitely faster than recursive solution for this problem (in Python). The reason is that they both "fill up" the same sub-solutions in the dp array, and recursion always has more overhead than iteration.

from dietpepsi's post and explanation by StrongerXi