My readable Python ~500ms accepted solution with explanation


  • 4

    Before started, I removed all balloons with number 0, and put an additional "1" at the beginning and end, for that based on the definition of this problem, one can imagine there're implicitly two "1" balloons at the beginning and end but would never be burst. The balloon array now becomes: [1,...,x,x,x,x,x,x,...,1], where the x's are original nonzero balloons.

    I feel the trickiest part is to sort out what you really need to calculate in each DP sub-problem. In each sub-problem I have 3 pointers "l", "m" and "r" located as below:

           l   m     r
      [...,x,x,x,x,x,x,...]
    

    I focus on the region (l,r), and assign m as the last balloon to be burst in this region. I need to calculate:

    • max coins after the balloons in region (l,m) are burst

    • max coins after the balloons in region (m,r) are burst

    • nums[l]*nums[m]*nums[r]

    Note I'm using exclusive region notation, which means the lth and rth balloons are not burst in this sub-problem.

    With each iteration I gradually increase the interval between balloons l and r. Such process is equivalent to beginning from the 1st burst balloon. As the interval to be considered increases, all the possible combination of sub-intervals within current interval would have been calculated in previous iterations.

    In the end I just return the regional max coins excluding the first and the last balloons, which are the 2 extra balloons I appended before started (now you can see why they're needed).

    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 xrange(len(nums))] for j in xrange(len(nums))]
        for balloons_to_burst in xrange(1, len(nums)-1): # number of balloons in (l,r) region
            for l in xrange(0, len(nums)-balloons_to_burst-1): # for m and r to be assigned legally
                r = l+balloons_to_burst+1
                for m in xrange(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]

  • 0
    P

    Thanks for the clear explanation, it is really helpful!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.