8.16 - hard - 61

312. Burst Balloons

这种题型被总结为区间DP，一般用从终点朝起点去考虑会容易些，然后解法是记忆化搜索。

class Solution(object):
    def maxCoins(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums = [1] + nums + [1]
        return self.search(nums, 1, len(nums)-2, set(), {})
        
    
    def search(self, nums, left, right, visited, m):
        if (left, right) in visited:
            return m[(left, right)]
        res = 0
        for k in range(left, right+1): # bomb k
            mid = nums[k]*nums[left-1]*nums[right+1]
            left_val = self.search(nums, left, k-1, visited, m)
            right_val = self.search(nums, k+1, right, visited, m)
            res = max(res, left_val+right_val+mid)
        
        visited.add((left, right))
        m[(left, right)] = res
        return res