312. Burst Balloons

Givennballoons, indexed from0ton-1. Each balloon is painted with a number on it represented by arraynums. You are asked to burst all the balloons. If the you burst ballooniyou will getnums[left] * nums[i] * nums[right]coins. Hereleftandrightare adjacent indices ofi. After the burst, theleftandrightthen 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;
        nums_pad[0] = nums_pad[n++] = 1;

        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],
                                dp[left][i] + nums_pad[left] * nums_pad[i] * nums_pad[right] + dp[i][right]
                                              );
                }
            }
        }

        return dp[0][n-1];
    }
}

class Solution {
public:
    int maxCoins(vector<int>& nums) {
         // first bursting 0s
        int nums_pad [nums.size() + 2]; 
        int n = 1;
        for (int x : nums) if( x > 0) nums_pad[n++] = x;
        nums_pad[0] = nums_pad[n++] = 1;

        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],
                                dp[left][i] + nums_pad[left] * nums_pad[i] * nums_pad[right] + dp[i][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]
        n = len(nums_pad)
        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):
                    dp[left][right] = max(dp[left][right], dp[left][i] + nums_pad[left] *nums_pad[i]* nums_pad[right] + dp[i][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;
        nums_pad[0] = nums_pad[n++] = 1;

        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