Bottom up+recursvie in python with explanation


  • 2
    S
     """Every element in the given list has two roles:
       1. as the element to disappear lastly
       2. as the boundary for the subarray if it will disappear lastly
    """
    def maxCoins(self, nums):#bottom up with rescursive
        nums = [1] + nums + [1]
        n = len(nums)
        dp = [[0]*n for _ in xrange(n)]#avoiding duplication
        #define the boundary
        def helper(left, right):
            if right-left <=1:#if there are 1 or 2 elements
                return 0
            if dp[left][right]:
                return dp[left][right]
            res = []
            for last in range(left+1, right):#choose which element to finish lastly and caculate sub array
                res.append(nums[left]*nums[last]*nums[right]+helper(left, last)+helper(last,right))
            dp[left][right] = max(res)
            return dp[left][right]
        return helper(0,len(nums)-1)

Log in to reply
 

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