LeetCode 312. 戳气球

2025-11-21 HGNULB 约 5 分钟

文章信息 12 个分类 2 个标签

分类

LeetCode CodeTop 困难已解决 10-20 字节跳动美团阿里巴巴快手腾讯猿辅导百度

题目描述

✅ 312. 戳气球

题意分析

一排气球各带一个数字，每戳破一个就拿走「它自己乘上当时紧挨着它的左右两个数字」这么多硬币，被戳破的气球从队列中消失，原本隔着它的两个气球随即变成邻居。要求把所有气球都戳破，问硬币总数最多是多少。

关键的约束信号是「相邻关系会随戳破动态变化」：同一个气球的收益不是固定值，取决于戳它的时刻还剩哪些邻居。这说明每一步的收益依赖此前所有决策，普通的贪心和前缀式递推都接不上。

数据规模只有几百个气球，这个量级容忍平方甚至立方级别的算法，反过来提示答案是一种在区间上做的递推，而不是线性扫描。

边界包括只有一个气球（答案就是它本身，左右都视为 1）、气球值为 0（戳它只拿 0 枚硬币，但它仍然会把两侧隔开）、以及最左和最右的气球缺少一侧邻居的情况。

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

核心思路

正向枚举“先戳谁”很难拆分子问题：气球消失后，左右两段会成为新的邻居，收益仍互相影响。反过来枚举一个区间里最后戳的气球，它被戳时区间内其他气球都已消失，左右邻居必然是区间两端，收益因此可以确定。

在数组两侧各补一个值为 1 的虚拟气球。定义 dp[left][right] 为戳完开区间 (left, right) 内所有气球能获得的最大硬币数，两端气球保留不动。若 mid 是这个区间最后被戳的气球，则：

dp[left][right] = max(dp[left][mid] + dp[mid][right] + points[left] * points[mid] * points[right])

左右子区间在 mid 尚未被戳时彼此隔开，可以独立求最优值；最后再获得三数乘积。状态依赖更短的区间，所以必须按区间长度从小到大计算。

正确性说明：任意最优戳法都有唯一的最后一个气球 mid，删除最后一步后，左右两侧分别形成两个独立子问题；若其中一侧不是最优方案，替换后可得到更大的总收益，与原方案最优矛盾。枚举所有 mid 后取最大值，因此不会漏掉全局最优解。

解题步骤

构造 points = [1] + nums + [1]，统一处理原数组两端。

初始化二维数组 dp；空开区间的收益自然为 0。

按跨度 length = 2...n+1 枚举 left 和 right = left + length。

枚举 mid ∈ (left, right)，把它视为最后戳的气球并更新 dp[left][right]。

返回 dp[0][n+1]。

以 [3,1,5,8] 为例，补边界后是 [1,3,1,5,8,1]。先得到只含一个气球的区间，再逐步合并到完整区间；完整区间最后枚举到保留 8 最后戳时，可得到最大值 167。

代码实现

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)$，主要是二维 DP 表。

关键点总结

“最后戳”让气球的左右邻居固定，是本题能拆成区间 DP 的关键。

dp[left][right] 表示开区间，两端只作为边界乘数，不能被当前状态戳掉。

转移使用 dp[left][mid] 和 dp[mid][right]，因此按短区间到长区间计算。

两端补 1 后，边界和普通区间使用同一套公式。

易错点总结

枚举第一个戳的气球后直接拆成左右两段：两段会在它消失后相邻，不能独立求解。

把状态误写成闭区间：若仍套用开区间转移，端点既被戳又被当作固定邻居，会重复计算。

区间遍历顺序错误：长区间依赖的短区间尚未计算，会读到默认值 0。

返回 dp[0][n]：补边界后的右端点是 n + 1，完整答案是 dp[0][n+1]。

mid 遍历到端点：最后被戳的只能是真实的区间内部气球，范围必须是 left + 1 到 right - 1。

相似题目

题目	难度	考察点
486. 预测赢家	中等	区间博弈与先后手差值
877. 石子游戏	中等	博弈区间 DP 与奇偶结论
887. 鸡蛋掉落	困难	最坏情况最优决策
1000. 合并石头的最低成本	困难	带分组约束的区间合并
1690. 石子游戏 VII	中等	前缀和配合区间博弈
面试题 08.14. 布尔运算	中等	按运算符切分表达式