Python Solution Using DP/Memorized-search


  • 0
    H

    Just paste my Accepted code here for reference, welcome comments and corrections :D

    Memorized-search

    def maxCoins(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            if not nums or len(nums) == 0: return 0
            self.memo = [[-1 for __ in xrange(len(nums)+2)] for _ in xrange(len(nums)+2)]
            return self.burst([1,] + nums + [1, ], 0,  len(nums)+1)
                
        def burst(self, balloons, left, right):
            if left + 2 > right: return 0
            if left + 2 == right:
                return balloons[left] * balloons[left+1] * balloons[right]
            if self.memo[left][right] != -1: return self.memo[left][right]
            ans = 0
            for i in xrange(left+1, right):
                ans = max(ans, balloons[i] * balloons[left] * balloons[right] + self.burst(balloons, left, i) + self.burst(balloons, i, right))
            self.memo[left][right] = ans
            return ans
    

    DP

    def maxCoins(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            if not nums or len(nums) == 0: return 0
            values = [1,] + nums + [1,]
            dp = [[0 for _ in values] for __ in values]
            
            for length in xrange(1, len(nums)+1):
                for left in xrange(0, len(nums)+1-length):
                    right = left + length + 1
                    new = 0
                    for last in xrange(left+1, right):
                        new = max(new, values[last]*values[left]*values[right] + dp[left][last] + dp[last][right])
                    dp[left][right] = new
            return dp[0][-1]
    

Log in to reply
 

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