戳气球 图解题解

戳气球这道题真正难在哪

题目给一排气球 nums，戳爆第 i 个能拿 nums[左邻] × nums[i] × nums[右邻] 枚硬币，戳爆之后它的左右两个邻居会接续相邻；数组两端越界的位置按值为 1 的气球算。求把气球全部戳完，最多能拿多少硬币。难点在于：每戳一个气球，剩下气球的邻居关系就变了，同一个气球在不同的戳法顺序里得分完全不同——顺序影响收益。

为什么枚举「先戳谁」的思路走不通

最直觉的想法是递归枚举第一个戳谁：戳掉它，剩下的气球接成新的一排，再对新排递归。但这条路有两个致命伤。其一，戳法顺序有 n! 种，纯枚举指数爆炸。其二，更本质的是子问题没法复用：先戳掉一个气球后，它两侧的气球变成邻居，后续每一步的得分都依赖你之前戳了谁，拆不出独立的子问题，动态规划无从下手。

症结在于先戳的气球会改变局面。那就反着问：有没有哪个决策，做出来之后不影响别人？

为什么倒过来枚举「最后戳谁」就能拆开

关键观察：对一段区间来说，与其想谁先被戳，不如想谁最后被戳。假设开区间 (i, j) 内最后戳爆的是位置 k——戳它的那一刻，区间内其他气球早都没了，k 的左右邻居必然就是边界 i 和 j，所以这一戳的硬币是 nums[i] × nums[k] × nums[j]，一个不依赖任何顺序的定值。

更妙的是，既然 k 最后才被戳，那么在此之前 k 一直立在原地当「隔板」：左半段 (i, k) 里的气球无论怎么戳，右邻居最多碰到 k，绝不会越过去碰到右半段；右半段同理。左右两半彻底解耦，各自独立求最优——这就是区间 DP 的典型思路。

dp 数组为什么定义成开区间、两端为什么补 1

先在原数组两端各补一个 1，得到 a = [1] + nums + [1]，这两个哨兵代表「越界处值为 1 的气球」，且永远不被戳，只当墙用——补了它们，nums[i] × nums[k] × nums[j] 这条公式对边界气球也成立，不用特判。

定义 dp[i][j] 为「戳光开区间 (i, j) 内全部气球能拿的最大硬币」，i、j 本身不戳。转移就是枚举区间内最后戳的位置 k：dp[i][j] = max(dp[i][k] + a[i] × a[k] × a[j] + dp[k][j])，k 取 i+1 到 j-1。填表必须按区间长度从短到长：dp[i][j] 依赖的 dp[i][k] 和 dp[k][j] 都是更短的区间，短的没算好，长的就没依据。答案是 dp[0][n-1]，即戳光整排原始气球；对示例 [3, 1, 5, 8]，这个值是 167。

戳气球的复杂度怎么算，哪里容易翻车

时间 O(n³)：区间 (i, j) 共约 n² 个，每个区间要枚举 O(n) 个候选 k。空间 O(n²)，存整张二维区间表。

两个高频翻车点：一是忘了两端补 1，边界气球的得分公式就会越界或算错；二是填表顺序按普通的行列双重循环来写，会在算长区间时用到还没填的短区间——正确写法是外层循环区间长度 L 从 2 到 n-1，内层再枚举左端点。记住「先戳会缠住、最后戳才独立」，转移方程可以自己推出来。

Python

def maxCoins(nums):
    a = [1] + nums + [1]
    n = len(a)
    dp = [[0]*n for _ in range(n)]
    for L in range(2, n):          # L = j - i
        for i in range(0, n - L):
            j = i + L
            for k in range(i+1, j):
                v = dp[i][k] + a[i]*a[k]*a[j] + dp[k][j]
                if v > dp[i][j]: dp[i][j] = v
    return dp[0][n-1]

C++

int maxCoins(vector<int>& nums){
    vector<int> a; a.push_back(1);
    for(int x: nums) a.push_back(x);
    a.push_back(1);
    int n = a.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for(int L = 2; L < n; L++)
        for(int i = 0; i + L < n; i++){
            int j = i + L;
            for(int k = i+1; k < j; k++)
                dp[i][j] = max(dp[i][j], dp[i][k] + a[i]*a[k]*a[j] + dp[k][j]);
        }
    return dp[0][n-1];
}

Java

int maxCoins(int[] nums){
    int m = nums.length, n = m + 2;
    int[] a = new int[n];
    a[0] = 1; a[n-1] = 1;
    for (int i = 0; i < m; i++) a[i+1] = nums[i];
    int[][] dp = new int[n][n];
    for (int L = 2; L < n; L++)
        for (int i = 0; i + L < n; i++) {
            int j = i + L;
            for (int k = i+1; k < j; k++)
                dp[i][j] = Math.max(dp[i][j], dp[i][k] + a[i]*a[k]*a[j] + dp[k][j]);
        }
    return dp[0][n-1];