Simple python dp solution with O(n^3) time, O(n^2) space


  • 0
    S
    class Solution(object):
        def maxCoins(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            nums = [1]+nums+[1]
            dp = [[0] * len(nums) for i in ' ' * len(nums)]
            for start in range(len(nums) - 2, 0, -1):
                for end in range(start, len(nums) - 1):
                    for k in range(start, end+1): #nums[k] is the last balloon in nums[start...end]
                        dp[start][end] = max(dp[start][end], dp[start][k-1] + dp[k+1][end] + nums[start-1] * nums[k] * nums[end+1])
            return dp[1][len(nums)-2]
    

Log in to reply
 

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