0312：戳气球（★★）

力扣第 312 题

题目

有 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：

输入：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：

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

提示：

• n == nums.length
• 1 <= n <= 300
• 0 <= nums[i] <= 100

相似问题：

• 1000：合并石头的最低成本（2422 分）

分析

• 为了方便，在前后各加一个数字 1 作为边界，得到数组 A
• 假设最后戳破第 k 个气球，获得 A[0]*A[k]*A[-1] 个硬币，剩下的转为 A[:k+1] 和 A[k:] 的递归子问题
• 因此采用区间 dp 即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        A = [1]+nums+[1]
        n = len(A)
        f = [[0]*n for _ in range(n)]
        for i in range(n-1,-1,-1):
            for j in range(i+2,n):
                for k in range(i+1,j):
                    f[i][j] = max(f[i][j],f[i][k]+f[k][j]+A[i]*A[j]*A[k])
        return f[0][-1]

2541 ms