有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。

求所能获得硬币的最大数量。

示例 1：

1
2
3
4
5
输入：nums = [3,1,5,8]
输出：167
解释：
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167

示例 2：

1
2
输入：nums = [1,5]
输出：10

用动态规划解决这道题，假设我们添加两个边缘的球值为1，我们每一次只戳这两个球的中间部分的球，最后戳一个球我们就能得到答案，我们将左边缘记作i，右边缘记作j，最后这个球记作k，那么我们得到的答案就是i到k之间戳掉的球加上k到j之间戳掉的球加上$num[i]nums[k]nums[j]$,对于一个长度为n的输入，我们不断循环，第一次求所有长度为的子数组的答案，第二次求所有长度为3的子数组答案（可以利用长度为2的子数组求出的答案），依次递推，直到求得长度为n的子数组得到的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def maxCoins(self,nums: List[int])->int:
        nums.insert(0,1)
        nums.insert(len(nums),1)
        store = [[0]*len(nums) for i in range(len(nums))]
        @cache
        def helper(i,j):#计算i，j之间的最大值
            m = 0
            for k in range(i+1,j):
                left = store[i][k]
                right = store[k][j]
                a = left + nums[i]*nums[k]*nums[j]+right
                if a > m:
                    m = a
            store[i][j] = m
        
        for n in range(2,len(nums)):
            for i in range(0,len(nums)-n):
                helper(i,i+n)
        return store[0][len(nums)-1]

由于一开始的插入操作，使得最小的数组长度为3(只输入一个数字的情况)，其他输入情况也是这样，输入n个数字，实际上我们是对n+2个数字进行处理。

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。