题目：有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。如果你戳破气球 i ，就可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。
求所能获得硬币的最大数量。
官方给的示例: [3,1,5,8]，数组前后有虚拟气球标签都为1，但不能戳破，便于计算。
最优解先破气球1的到3*1*5=15， 数组[3,1,5,8] 变为 [3,5,8]
再破气球5得到3*5*8=120，数组[3,5,8]变为[3,8]
然后破气球3得到1*3*8=24，最后破气球8
总计 coins = 3*1*5 3*5*8 1*3*8 1*8*1 = 167
这个题目有很多解法，我个人倾向于动态规划，这个思路对于我比较清晰。
首先，对数组进行分解，通过求解子问题，来获得最终的结果。
然后，列出状态转移方程。以官方的数据为例，如图所示：
最后就是按照上面的思路进行编码。代码如下：
class Solution:
def maxCoins(self, nums: List[int]) -> int:
dp=[[0] * (len(nums) 2) for _ in range(len(nums) 2)]
userlist=[1] nums [1]
for i in range(len(nums)-1,-1,-1):
for j in range(i 2,len(nums) 2):
for mid in range(i 1,j):
dp[i][j]=max(dp[i][j],dp[i][mid] dp[mid][j] userlist[mid]*userlist[i]*userlist[j])
return (dp[0][len(nums) 1])
