题目：

  1. 312. 戳气球
  2. 有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
  4. 现在要求你戳破所有的气球。如果你戳破气球 i ，
  5. 就可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。
  7. 求所能获得硬币的最大数量。
  9. 说明:
  11. 你可以假设 nums[-1] = nums[n] = 1，但注意它们不是真实存在的所以并不能被戳破。
  12. 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
  13. 示例:
  15. 输入: [3,1,5,8]
  16. 输出: 167 
  17. 解释: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
  18.      coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

答案：

时间：

1h，差点没想通

  1. class Solution:
  2.     def maxCoins(self, nums: List[int]) -> int:
  3.         nums=[1]+nums+[1]
  4.         n=len(nums)
  5.         dp=[[0]*(n) for _ in range(n)]
  7.         for i in range(n-3,-1,-1):
  8.             for j in range(i+2,n):
  9.                 for k in range(i+1,j):
  10.                     dp[i][j]=max(dp[i][j],nums[i]*nums[k]*nums[j]+dp[i][k]+dp[k][j])
  11.         return dp[0][n-1]

要点：

1. dp 定义：区间dp

区间dp首先是个开区间
其次这里区间大小至少为3，因为中间是开区间，至少要取到1.
遍历开区间迭代的时候，遍历的值都在开区间内取到，不会取到边界。
区间dp，要先有小区间，才能迭代大区间，所以 i 的遍历是倒序遍历

其他：

代码报错：无