题目

戳气球

直觉

戳破气球时，不会影响其他气球的得分，且列表长度始终在减少。这意味着我们可以用动态规划来解决这道题。

思路

考虑这样一种定义：$dp[i][j]$ 表示戳破 i 到 j 之间所有气球所能获得的最大得分。在这种情况下，如果 n 是列表长度，那么答案就是 $dp[0][n-1]$。

现在来思考如何求得 $dp[i][j]$。正如我们在直觉部分提到的，气球数量始终在减少，这意味着我们可以先计算较短区间的结果，再逐步扩展区间到 $0 \to n-1$。

由此得出我们的解法：

首先，遍历区间长度。

接着，将区间 $i \to j$ 拆分为两个子区间 $i \to k-1$ 和 $k+1 \to j$。

然后，将子区间 $i \to k-1$、$k+1 \to j$ 的得分相加，再加上戳破第 k 个气球的得分，即可计算出区间 $i \to j$ 的总得分。

由于子区间 $i \to k-1$ 和 $k+1 \to j$ 中的气球已经全部被戳破，所以戳破第 k 个气球的得分增量为 $nums[k] \times nums[i-1] \times nums[j+1]$。

最后需要注意子区间边界的处理：由于当前戳破的气球可以是区间 $i \to j$ 的边界，因此 k 需要在 $[i, j]$ 上闭区间遍历。

最终答案即为 $dp[0][n-1]$。

复杂度

  • 时间复杂度：$O(N^3)$，N 为列表长度。
  • 空间复杂度：$O(N^2)$，N 为列表长度。

代码

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        n = len(nums)
        nums = nums + [1]
        dp = [[0 for _ in range(n+1)] for _ in range(n+1)]

        for i in range(n):
            dp[i][i] = nums[i] * nums[i-1] * nums[i+1]

        for i in range(1, n):
            for l in range(n):
                if i + l == n:
                    break
                r = i + l
                for k in range(l, r+1):
                    dp[l][r] = max(dp[l][r], dp[l][k-1] + dp[k+1][r] + nums[k] * nums[l-1] * nums[r + 1])

        # print(dp)

        return dp[0][n-1]

image.png