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

### # Solution

Approach 1: backtracking.

Approach 2: DP + divide and conquer.

### # Code (Python)

Approach 2:

def maxCoins(self, nums: List[int]) -> int:
# goal(i, j) -- max coins from nums[i] to nums[j], exclusive of i and j
if not nums:
return 0
nums = [1] + nums + [1]

@lru_cache(None)
def burst(start, end):
if start == end:
return 0
result = 0
for last_burst in range(start + 1, end):
result = max(result, burst(start, last_burst) + burst(last_burst, end) + nums[start] * nums[last_burst] * nums[end])
return result

return burst(0, len(nums) - 1)

# OR without lru_cache (has to specify an order to fill in the table)
def maxCoins(self, nums: List[int]) -> int:
if not nums:
return 0
nums = [1] + nums + [1]
table = [[0] * len(nums) for _ in range(len(nums))]

for distance in range(2, len(nums)):
for left in range(len(nums) - distance):
right = left + distance
for last_burst in range(left + 1, right):
table[left][right] = max(table[left][right], table[left][last_burst] + table[last_burst][right] + nums[left] * nums[last_burst] * nums[right])

return table[0][-1]

### # Code (C++)

Approach 1:

// Top-down with memorization.
class Solution {
private:
vector<vector<int>> points;
int doMaxCoins(vector<int>& nums, int head, int tail, int prev, int next) {
return 0;
for (int i = head; i <= tail; ++i)
{
// this is wrong.
//                nums[i] *
//                ((i > head) ? nums[i-1] : prev) *
//                ((i < tail) ? nums[i+1] : next) +
//                doMaxCoins(nums, head, i-1, prev, (i+1 < tail) ? nums[i+1] : next) +
//                doMaxCoins(nums, i+1, tail, (i-1 > head) ? nums[i-1] : prev, next));
doMaxCoins(nums, head, i-1, prev, (i <= tail) ? nums[i] : next) +
doMaxCoins(nums, i+1, tail, (i >= head) ? nums[i] : prev, next) +
nums[i] * prev * next);
}
}
public:
int maxCoins(vector<int>& nums) {
int n = nums.size();
points = vector<vector<int>>(n, vector<int>(n, 0));
return doMaxCoins(nums, 0, n-1, 1, 1);
}
};

Approach 2:

// Bottom-up.
class Solution {
public:
int maxCoins(vector<int>& nums) {
nums.insert(nums.begin(), 1);
nums.push_back(1);
int n = nums.size();
vector<vector<int>> points;
points = vector<vector<int>>(n-1, vector<int>(n, 0));
for (int len = 1; len <= n-2; ++len)
{
{
int tail = head + len - 1;