312. Burst Balloons

gistfile1.txt

class Solution:
    def maxCoins(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums: return 0
        
        return self.sol_dp(nums)
        return self.rec(nums)
    
    def sol_dp(self, nums):
        nums = [1] + nums + [1]
        mem = [[-1 for _ in nums] for _ in nums]
        for i in range(1, len(nums)):
            mem[i-1][i] = 0
        
        for k in range(2, len(nums)):
            for l in range(0, len(nums)-k):
                r = l + k
                for i in range(l+1, r):
                    mem[l][r] = max(mem[l][r], mem[l][i] + mem[i][r] + nums[l]*nums[i]*nums[r])

        return mem[0][len(nums)-1]

        
    def rec(self, nums):
        nums = [1] + nums + [1]
        mem = [[-1 for _ in nums] for _ in nums]
        
        def mc(l, r):
            if mem[l][r] != -1:
                return mem[l][r]
            ans = 0
            for i in range(l+1, r):
                ans = max(ans, mc(l, i) + mc(i, r) + nums[l]*nums[i]*nums[r])
            mem[l][r] = ans
            return ans

        ans = mc(0, len(nums)-1)
        return ans