LeetCode 312. 戳气球

约 5 分钟
文章信息 12 个分类 2 个标签
分类
LeetCode CodeTop 困难 已解决 10-20 腾讯 字节 阿里 美团 百度 快手 猿辅导
标签
数组 动态规划

题目描述

✅ 312. 戳气球

image-20260928220558843

题意分析

将所有气球依次戳破，戳破某个气球时，获得它与当时仍存在的左右相邻气球的数值乘积。某一侧已经没有气球时，该侧按数值 1 计算，求整段过程能够获得的最大硬币数。

这里的相邻关系会随着气球消失而改变，不是始终使用原数组的左右两个位置。所有气球最终都要戳破，但可以选择顺序；不同顺序会改变后续收益，所以不能只挑当前乘积最大的气球。

解法：区间 DP 枚举最后戳的气球

核心思路

[!blue]

若先决定戳破区间中的哪个气球，它消失后左右两段会连在一起，后续收益相互影响，不能直接把两段独立求解。反过来决定“区间内最后戳谁”，这个气球在此前一直保留，就能作为屏障，将左右两边隔开。

在数组两端补数值 1，它们只作为边界，不参与戳破。定义 dp[left][right] 为：保留两端气球，把开区间 (left, right) 内所有气球戳完的最大收益。这个定义固定了子问题外部仍存在的相邻边界。

假设 mid 是最后戳破的内部气球。在它被戳之前，左侧只受 left、mid 两个边界影响，右侧只受 mid、right 两个边界影响，分别得到 dp[left][mid] 与 dp[mid][right]。两侧都清空后，mid 的相邻气球恰好就是两端，最后一次获得 points[left] * points[mid] * points[right]。

三部分相加就是固定最后位置的最优收益。任意戳破顺序都有一个最后位置，而每个位置对应的两侧最优方案也能依次执行，再最后戳它，所以枚举所有 mid 并取最大值，既不会漏掉最优顺序，也不会组合出不可执行的收益。

两个子区间的跨度都比当前区间小，因此按跨度从小到大填表。相邻边界之间没有内部气球，收益为零；跨度从二开始时，才包含一个需要戳破的气球。

解题步骤

  1. 创建长度为 n + 2 的 points，首尾填 1，原数组放在下标 1 到 n。
  2. 创建全零的二维 dp，让空开区间的收益自然为零。
  3. 从跨度 length = 2 到 n + 1 逐步扩大区间，取 right = left + length。
  4. 对每个内部位置 mid，计算两侧最优收益与最后一次乘积之和，更新 dp[left][right]。
  5. 返回 dp[0][n + 1]，它包含全部真实气球，两端虚拟边界始终保留。

代码实现

class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[] points = new int[n + 2];

        points[0] = points[n + 1] = 1;
        System.arraycopy(nums, 0, points, 1, n);

        int[][] dp = new int[n + 2][n + 2];

        // 这里长度是边界下标差，跨度二才包含一个真实气球。
        for (int length = 2; length <= n + 1; length++) {
            for (int left = 0; left + length <= n + 1; left++) {
                int right = left + length;

                for (int mid = left + 1; mid < right; mid++) {
                    // 假定当前气球最后戳，两侧先独立完成，最后边界仍然存在。
                    int coins =
                            dp[left][mid]
                                    + dp[mid][right]
                                    + points[left] * points[mid] * points[right];

                    dp[left][right] = Math.max(dp[left][right], coins);
                }
            }
        }

        return dp[0][n + 1];
    }
}

func maxCoins(nums []int) int {
    n := len(nums)
    points := make([]int, n+2)
    points[0], points[n+1] = 1, 1
    copy(points[1:], nums)

    dp := make([][]int, n+2)
    for i := range dp {
        dp[i] = make([]int, n+2)
    }
    // 这里长度是边界下标差，跨度二才包含一个真实气球。
    for length := 2; length <= n+1; length++ {
        for left := 0; left+length <= n+1; left++ {
            right := left + length
            for mid := left + 1; mid < right; mid++ {
                // 假定当前气球最后戳，两侧先独立完成，最后边界仍然存在。
                coins := dp[left][mid] + dp[mid][right] +
                    points[left]*points[mid]*points[right]
                if coins > dp[left][right] {
                    dp[left][right] = coins
                }
            }
        }
    }
    return dp[0][n+1]
}

复杂度分析

  • 时间复杂度：$O(n^3)$，共有 $O(n^2)$ 个边界区间，每个区间最多枚举 $O(n)$ 个最后位置。
  • 空间复杂度：$O(n^2)$，二维状态表占主导，补充边界的数组占 $O(n)$。

关键点总结

[!green]

  • 最后戳的气球在此前持续分隔两侧，才使左右子问题可以独立计算。
  • 状态处理开区间内部，两个端点保留作为邻居，不计入当前戳破范围。
  • 枚举最后位置覆盖所有可能顺序，左右最优收益加上最后一次收益形成转移。
  • 按跨度递增，确保需要的两个更短区间已经计算完成。

易错点总结

[!yellow]

  • 枚举第一个戳破的气球后，就把左右两边独立求最优，忽略它消失后两边会成为邻居。
  • 将状态解释为闭区间，却仍把端点作为最后乘积的固定邻居，混淆哪些气球已经戳破。
  • 优先计算长区间，依赖的短区间还没有求解，读到的零值不代表实际最优收益。
  • 将 length 当作内部气球个数；代码中它是两端下标之差，内部数量为 length - 1。
  • 枚举 mid 时包含两端，等于把应保留的边界也戳掉。
  • 返回未覆盖右侧虚拟边界的状态，漏掉部分真实气球；完整答案的右边界是 n + 1。

相似题目

题目 难度 关联与区别
1039. 多边形三角剖分的最低得分 中等 同样以区间分割点及两端元素构成三项乘积代价，再组合左右子区间。
1547. 切棍子的最小成本 困难 同样枚举决定区间独立性的那一步，原题选第一刀，本题倒过来选最后戳破的气球。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/20746903
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！