# 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) {
        if (head > tail)
            return 0;
        if (points[head][tail] > 0)
            return points[head][tail];
        for (int i = head; i <= tail; ++i)
        {
// this is wrong.
//            points[head][tail] = std::max(points[head][tail],
//                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));
            points[head][tail] = std::max(points[head][tail],
                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);
        }
        return points[head][tail];
    }
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)
        {
            for (int head = 1; head+len < n; ++head)
            {
                int tail = head + len - 1;
                for (int i = head; i < head+len; ++i)
                {
                    points[len][head] = std::max(points[len][head],
                        points[i-head][head] +
                        points[tail-i][i+1] +
                        nums[i] * nums[head-1] * nums[tail+1]);
                }
            }
        }
        return points[n-2][1];
    }
};