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 的气球。

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

数据范围：

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

示例

示例 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

核心思路

朴素想法：枚举第一个戳破哪个气球，然后递归处理剩下的。

问题：戳破一个气球后，左右气球变为相邻，后续的得分依赖于当前剩余的气球。这个依赖关系很复杂，很难拆分。

关键技巧：反过来看——不是枚举「先戳哪个」，而是枚举「最后戳哪个」。

• 假设区间 (i, j)（开区间）内所有气球都被戳破，且 i、j 始终存在；
• 令 k 是区间内最后一个被戳破的气球；
• 那么 k 被戳破时，它的左右邻居恰好是 i 和 j（因为中间其他气球都已被戳破）；
• 此时得分为 val[i] * val[k] * val[j]；
• 并且问题被拆成两个独立的子问题：区间 (i, k) 和区间 (k, j)。

为什么要两边加哨兵 1：

• 题目说超出边界的气球算作 1；
• 在数组两端各加一个虚拟气球 1，就不需要特判边界；
• 得到新的数组 val = [1] + nums + [1]。

状态定义：dp[i][j] 表示「填满开区间 (i, j)（即戳破 i 和 j 之间的所有气球）能获得的最大硬币数」。

转移方程：

$$dp[i][j] = \max_{i < k < j} \left( val[i] \times val[k] \times val[j] + dp[i][k] + dp[k][j] \right)$$

边界：i >= j - 1 时，开区间内没有气球，dp[i][j] = 0。

答案：dp[0][n+1]（开区间 (0, n+1) 覆盖整个数组）。

---

方法一：记忆化搜索（自顶向下）

思路及解法

用递归函数 solve(i, j) 表示「戳破开区间 (i, j) 内所有气球能获得的最大硬币数」。

递归过程：

1. 若 i >= j - 1，区间内无气球，返回 0；
2. 否则枚举 k ∈ (i, j) 作为最后戳破的气球：
   • 得分 val[i] * val[k] * val[j]；
   • 递归求 solve(i, k) + solve(k, j)；
   • 取所有 k 中的最大值。

用 lru_cache 记忆化：同一个 (i, j) 只会被计算一次，避免重复。

为什么「最后戳破」的思路是对的：

• 反过来看，每次相当于「添加一个气球」；
• 最后一个添加的气球 k，它两侧的边界 i、j 一定是已经存在的；
• 添加 k 时，k 的左右邻居只能是 i 和 j；
• 因此得分只依赖于 i, j, k，与中间过程无关；
• 而添加 k 后，问题完全拆成 (i, k) 和 (k, j) 两个独立的子问题。

代码

from functools import lru_cache

class Solution:
    def maxCoins(self, nums: list[int]) -> int:
        n = len(nums)
        val = [1] + nums + [1]     # 两端加哨兵

        @lru_cache(maxsize=None)
        def solve(left: int, right: int) -> int:
            # 开区间 (left, right) 内无气球
            if left >= right - 1:
                return 0

            best = 0
            # 枚举最后戳破的气球 k
            for k in range(left + 1, right):
                total = val[left] * val[k] * val[right]
                total += solve(left, k) + solve(k, right)
                best = max(best, total)

            return best

        return solve(0, n + 1)

复杂度分析

• 时间复杂度：$O(n^3)$，区间数 $O(n^2)$，每个区间枚举 $O(n)$ 个分割点。
• 空间复杂度：$O(n^2)$，缓存 $O(n^2)$ 个状态。

---

方法二：动态规划（自底向上）✅ 推荐

思路及解法

把方法一改为自底向上填表。

状态定义：dp[i][j] 表示「戳破开区间 (i, j) 内的所有气球能获得的最大硬币数」。

转移方程：

$$dp[i][j] = \max_{i < k < j} \left( val[i] \times val[k] \times val[j] + dp[i][k] + dp[k][j] \right)$$

边界：dp[i][j] = 0，当 i >= j - 1。

遍历顺序：dp[i][j] 依赖 dp[i][k] 和 dp[k][j]，其中 k ∈ (i, j)。所以：

• i 从大到小枚举（n-1 到 0）；
• j 从小到大枚举（i+2 到 n+1）；
• 或按区间长度从小到大枚举。

答案：dp[0][n+1]。

代码

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

        # i 从大到小
        for i in range(n - 1, -1, -1):
            # j 从小到大
            for j in range(i + 2, n + 2):
                for k in range(i + 1, j):
                    total = val[i] * val[k] * val[j]
                    total += dp[i][k] + dp[k][j]
                    dp[i][j] = max(dp[i][j], total)

        return dp[0][n + 1]

复杂度分析

• 时间复杂度：$O(n^3)$，状态数 $O(n^2)$，每个状态枚举 $O(n)$ 个分割点。
• 空间复杂度：$O(n^2)$。

---

两种方法对比

方法	时间	空间	特点
记忆化搜索	$O(n^3)$	$O(n^2)$	思路自然，从「最后戳」出发
动态规划	$O(n^3)$	$O(n^2)$	状态更清晰，效率稳定

推荐：

• 面试开场：先讲记忆化搜索，因为它直接对应「最后戳破某个气球」的思路，非常直观；
• 正式写代码：用DP，避免递归开销，也更符合区间 DP 的模板。

---

关键细节

1. 为什么是「最后戳破」而不是「最先戳破」

如果枚举「最先戳破哪个」：

• 戳破之后左右气球相邻，后续得分依赖中间过程；
• 子问题互相干扰，无法独立拆分。

如果枚举「最后戳破哪个」：

• 此时区间内其他气球都已经戳破，两侧的边界 i 和 j 一定存在；
• 最后戳破 k 时，它的左右邻居恰好是 i 和 j；
• 得分 val[i] * val[k] * val[j] 与中间过程无关；
• 左右两侧变成完全独立的子问题。

这是本题最重要的思维转换。

2. 哨兵 1 的作用

题目规定「超出边界的气球算作 1」。我们在两端加虚拟气球 1，好处：

• 不需要特判边界；
• 边界条件统一为 val[0] = val[n+1] = 1；
• 答案直接是 dp[0][n+1]。

3. 状态定义是「开区间」

dp[i][j] 表示开区间 (i, j) 内部的气球全部被戳破，i 和 j 本身不戳破。

这是为了让 i 和 j 成为最后戳破某个气球时的邻居。

4. 边界条件 i >= j - 1

开区间 (i, j) 内没有气球时（j - i <= 1），得分为 0。

5. DP 遍历顺序

dp[i][j] 依赖 dp[i][k]（更小的右端点）和 dp[k][j]（更大的左端点）。

• i 从大到小：保证 dp[k][j] 中 k > i 的已算好；
• j 从小到大：保证 dp[i][k] 中 k < j 的已算好。

也可以用「按区间长度从小到大」的写法，更符合区间 DP 的通用套路。

6. 区间 DP 的通用模板

for length in range(2, n + 1):
    for i in range(0, n - length + 1):
        j = i + length - 1
        for k in range(i + 1, j):
            dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + ...)

本题的 dp[i][j] 是最经典的区间 DP 形态。

7. 与 LC 1039（多边形三角剖分）的关系

两题的 DP 结构几乎一模一样：

• 都是「枚举区间内最后一个操作的元素」；
• 都是「独立拆成左右两个子问题」；
• 都是区间 DP 的模板。

学完本题可以直接套用 LC 1039。

---

总结

• 核心转换：把「先戳哪个」转成「最后戳哪个」；
• 状态定义：dp[i][j] 表示戳破开区间 (i, j) 内所有气球的最大得分；
• 转移方程： $$dp[i][j] = \max_{i < k < j} \left( val[i] \times val[k] \times val[j] + dp[i][k] + dp[k][j] \right)$$
• 哨兵技巧：在数组两端各加一个 1，避免边界特判；
• 遍历顺序：i 从大到小、j 从小到大（或按区间长度从小到大）；
• 答案：dp[0][n+1]；
• 时间/空间：都是 $O(n^2)$ 空间、$O(n^3)$ 时间；
• 通用套路：「相邻元素不断变化」→ 反过来想，枚举「最后操作的元素」。

相关题目

• LC 1039. 多边形三角剖分的最低得分（同款区间 DP）
• LC 516. 最长回文子序列（区间 DP）
• LC 1000. 合并石头的最低成本（区间 DP + 前缀和）
• LC 1547. 切棍子的最小成本（区间 DP）
• LC 664. 奇怪的打印机（区间 DP）