目录

0312:戳气球(★★)

力扣第 312 题

题目

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

现在要求你戳破所有的气球。戳破第 i 个气球,你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1i + 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

相似问题:

分析

  • 为了方便,在前后各加一个数字 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