https://leetcode.com/problems/burst-balloons/description/
一串数字，取出某一个时就把它和周围两个数（一共三个数）相乘，求按照什么顺序取完所得结果最大。
这个站在既成的dp思想上很好理解，但是自己凭空想，怎么也想不出来。
dp的之前计算基础是什么呢？确定0～x需要0～(x-1)吗？不是的。这是一维的存储结果。
最终发现这个dp需要二维。从中间分成两部分求和。
那么如果枚举第一个是哪个气球的话，是很难做到的，因为第一个取出来之后，左右两侧相邻了，相邻的结果左右了接下来怎么取，情况就爆炸了。
结果是枚举最后一个取哪一个，这样直接用最后一个乘以两头外边界就ok，又确保了被它隔开的两段的外边界是确定了。
class Solution:def maxCoins(self, nums):""":type nums: List[int]:rtype: int"""# nums.append(1)nums=[1]+numsnums.append(1)l=len(nums)dp=[[None]*l for i in range(l)]def update(i,j):if i==j:return nums[i-1]*nums[i]*nums[i+1]if i>j:return 0if dp[i][j]!=None:return dp[i][j]maxx=-1for x in range(i,j+1):a=update(i,x-1)+update(x+1,j)+nums[x]*nums[i-1]*nums[j+1]maxx=max(a,maxx)dp[i][j]=maxxreturn maxxreturn update(1,l-2)
