8 lines of Python code, O(n^3) time, O(n^2) space, recursive.

  • 0

    I recommend you to read through the most voted solution from dietpepsi. He explained very clearly how to approach this problem. I will give more details on the solution soon. The code below uses divide and conquer and recursion with memoization.

    def h(self, nums, l, r, d):
        if (l,r) not in d:
            d[(l,r)] = 0
            for i in range(l, r+1):
                d[(l,r)] = max(d[(l,r)], self.h(nums, l, i-1, d) + self.h(nums, i+1, r, d) + nums[i]*nums[l-1]*nums[r+1])
        return d[(l,r)]
    def maxCoins(self, nums):
        return self.h([1]+nums+[1], 1, len(nums), {})

Log in to reply

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