My TLE Python O(N^3) DP Solution with comments


  • 2
    C

    class Solution(object):

    def maxCoins(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        nums.insert(0, 1)
        nums.append(1)
        # table[i][j] stores the optimal result of bursting balloon starts at i and the length is j
        # balloon starts from 1 to n
        table = [[0 for i in xrange(n-I+1)] for I in xrange(n+1)]
        table.insert(0, []) 
    
        for i in xrange(1, n+1):
            table[i][1] = nums[i-1] * nums[i] * nums[i+1]
    
        for l in xrange(2, n+1): # length from 2 to n
            for j in xrange(1, n-l+2): # balloon can starts from balloon 1 to balloon n-l+1
                maximum = 0
                for i in xrange(j, j+l): # balloon i is the last burst balloon
                    if i < j+l-1:
                      temp = table[j][i-j] + table[i+1][j+l-i-1] + nums[i]*nums[j-1]*nums[j+l]
                    else:
                      temp = table[j][i-j] + nums[i]*nums[j-1]*nums[j+l]
                    maximum = max(maximum, temp)
                table[j][l] = maximum
        return table[1][n]

  • 0
    Z

    I think they changed the test cases so this solution can pass now.


Log in to reply
 

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