leetcode

Burst Balloons

Burst Balloons

gap version - 504ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def maxCoins(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums = [1]+[n for n in nums if n!=0]+[1]
        regional_max_coins = [[0 for i in range(len(nums))] for j in range(len(nums))]
        for balloons_to_burst in range(1, len(nums)-1): # number of balloons in (l,r) region
            for l in range(0, len(nums)-balloons_to_burst-1): # for m and r to be assigned legally
                r = l+balloons_to_burst+1
                for m in range(l+1,r):
                    regional_max_coins[l][r] = max(regional_max_coins[l][r], regional_max_coins[l][m]+regional_max_coins[m][r]+nums[l]*nums[m]*nums[r])
        return regional_max_coins[0][-1]

leet code