LC 312

Solution to LeetCode 312 Burst Balloons

LeetCode 312

Burst Balloons (Hard). [link]

1. Recursion with Memoization (Top Down). (TLE). Time complexity O(n^3). Space complexity O(n^2).

class Solution(object):
    def maxCoins(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        val = [1] + nums + [1] # padding
        
        def Recursion(l, r):
            if l >= r -1:
                return 0
            
            MAX = 0
            for i in range(l + 1, r):
                total = val[l] * val[i] * val[r]
                total += Recursion(l, i) + Recursion(i, r)
                MAX = max(MAX, total)
                
            return MAX
        
        return Recursion(0, n+1)

2. Dynamic Programming (Bottom Up). Find a index k and burst the left half val[i][k-1] and right half val[k+1][j] balloons to get the max sum, so that after bursting the k’th balloon, we get the max sum.

   Time complexity O(n^3). Space complexity O(n^2).

class Solution(object):
    def maxCoins(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        val = [1] + nums + [1] # padding
        dp = [[ 0 for _ in range(n+2)] for _ in range(n+2)]
        
        for l in range(1, n+1):
            for i in range(1, n-l+1 +1): # i is the start pt
                j = i + l - 1 # j is the end pt
                for k in range(i, j+1):
                    dp[i][j] = max(dp[i][j], dp[i][k-1] + val[i-1] * val[k] * val[j+1] + dp[k+1][j])
        return dp[1][n]