312. Burst Balloons
這種題型被總結(jié)為區(qū)間DP右遭，一般用從終點(diǎn)朝起點(diǎn)去考慮會(huì)容易些，然后解法是記憶化搜索缤削。
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
