跳至主要內容

戳气球——区间DP的逆向思维（最后一个而不是第一个）

老张2026/4/30大约 9 分钟

戳气球——区间DP的逆向思维（最后一个而不是第一个）

适读人群：Java后端工程师、区间DP进阶学习者 | 阅读时长：约22分钟 | 难度：Hard

开篇故事

戳气球是我做DP题目里思维最跳跃的一道。不是因为代码难，而是因为那个"逆向思维"的关键一跳，第一次做的时候完全想不到。

我最开始做这道题，用的是正向思维：第一个戳哪个气球？枚举第一个，然后递归处理剩下的。结果发现状态根本定义不了——因为戳掉第一个气球之后，原来的相邻关系变了，左右邻居合在一起了，而且是哪两个变成相邻完全取决于戳的顺序。这个状态太复杂，根本没法DP。

卡了好久，最后看了解题思路才恍然大悟：不要想第一个戳哪个，要想区间里最后一个戳哪个。

最后戳的那个气球，它的左右邻居是固定的——就是这个区间的两个边界！这样，区间的两端在整个处理过程中都不会消失（因为它们是最后才处理的），状态就稳定了。

这个思维转换，是戳气球这道题的灵魂，也是区间DP里最经典的技巧之一。

一、题目解析

题号：LeetCode 312. Burst Balloons

题目描述：有 n 个气球，编号为 0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。戳破气球 i 时，你可以获得 nums[i-1] * nums[i] * nums[i+1] 个硬币（i-1 和 i+1 是相邻气球，如果 i-1 或 i+1 超出数组边界，就把它当作 1）。

求戳破所有气球最多能获得多少硬币。

示例：

  • 输入：nums = [3,1,5,8]，输出：167
    • 戳 1：3×1×5=15，剩余[3,5,8]
    • 戳 5：3×5×8=120，剩余[3,8]
    • 戳 3：1×3×8=24，剩余[8]
    • 戳 8：1×8×1=8，剩余[]
    • 总计：15+120+24+8=167

数据范围：n == nums.length，1 ≤ n ≤ 300，0 ≤ nums[i] ≤ 100

二、DP思路推导

2.1 正向思维为什么失败

如果尝试"枚举第一个戳的气球"，设第一个戳的是 k（i < k < j），那么戳破 k 后，左侧和右侧的状态是独立的吗？

不是！ 因为戳破 k 后，k 的两侧气球变成了相邻，接下来戳任何一侧的气球都会用到另一侧。状态之间相互耦合，无法独立求解。

2.2 逆向思维的关键

关键思维转换：不枚举第一个戳的，枚举区间 (i, j) 内最后一个戳的气球 k。

为什么最后一个戳的气球，状态是清晰的？

因为：在戳 k 之前，区间 (i, k) 内的气球都已经戳完了，区间 (k, j) 内的气球也都已经戳完了。此时只剩下 k 还在区间里，它的左邻居是 i，右邻居是 j（边界固定！）。

所以，最后戳 k 获得的硬币 = nums[i] * nums[k] * nums[j]（i 和 j 在整个过程中都没被戳掉，它们是区间的边界）。

这就是戳气球的核心：把区间的两个端点视为"永远存在的边界"，枚举最后一个戳的气球。

2.3 状态定义

为了处理数组边界（nums[-1] 和 nums[n] 视为1），先在数组两端添加哨兵1：

扩展数组：arr[0] = 1, arr[1..n] = nums[0..n-1], arr[n+1] = 1

定义 dp[i][j] = 戳破开区间 (i, j) 内所有气球能获得的最大硬币数

注意：(i, j) 是开区间，i 和 j 本身不被戳，只戳 i 和 j 之间的气球。

最终答案为 dp[0][n+1]，即戳破全部 n 个气球的最大收益。

2.4 状态转移方程推导

对于区间 (i, j)，枚举最后戳破的气球 k（i < k < j）：

  1. 最后戳 k 之前，左半部分 (i, k) 的气球都已戳完，收益为 dp[i][k]
  2. 最后戳 k 之前，右半部分 (k, j) 的气球都已戳完，收益为 dp[k][j]
  3. 最后戳 k，收益为 arr[i] * arr[k] * arr[j]（此时 i 和 j 是 k 的唯一邻居）
dp[i][j] = max over k in (i,j): dp[i][k] + dp[k][j] + arr[i] * arr[k] * arr[j]

2.5 边界条件

  • dp[i][j] = 0，当 j == i+1（区间内没有气球，开区间(i, i+1)为空）
  • Java 默认初始化为0，自然满足

2.6 遍历顺序

和普通区间DP一样，按区间长度从小到大枚举。

外层：区间长度 len 从 2 到 n+1
内层：左端点 i 从 0 到 n+1-len
右端点：j = i + len
k 从 i+1 到 j-1

2.7 状态转移示意（nums=[3,1,5,8]）

扩展数组：arr = [1, 3, 1, 5, 8, 1]（索引0到5）

dp[i][j] = 戳破区间(i,j)内气球的最大收益

len=2（空区间，无气球）：dp[*][*] = 0

len=3（一个气球）：
  dp[0][2]: k=1, arr[0]*arr[1]*arr[2]=1*3*1=3, dp[0][2]=3
  dp[1][3]: k=2, 3*1*5=15, dp[1][3]=15
  dp[2][4]: k=3, 1*5*8=40, dp[2][4]=40
  dp[3][5]: k=4, 5*8*1=40, dp[3][5]=40

len=4（两个气球）：
  dp[0][3]: k=1: dp[0][1]+dp[1][3]+1*3*5=0+15+15=30
            k=2: dp[0][2]+dp[2][3]+1*1*5=3+0+5=8
            取max=30... （手动推导略）

最终dp[0][5] = 167 ✓

三、解法一：区间DP（按长度枚举）

public class BurstBalloons {
    
    /**
     * 312. 戳气球 - 区间DP（逆向思维）
     * 时间复杂度：O(n^3)
     * 空间复杂度：O(n^2)
     */
    public int maxCoins(int[] nums) {
        int n = nums.length;
        
        // 构建扩展数组，两端添加哨兵1
        int[] arr = new int[n + 2];
        arr[0] = arr[n + 1] = 1;
        for (int i = 0; i < n; i++) arr[i + 1] = nums[i];
        
        int len = n + 2;  // 扩展数组的长度
        
        // dp[i][j] = 戳破开区间(i,j)内所有气球的最大收益
        int[][] dp = new int[len][len];
        
        // 按区间长度从小到大枚举（注意：长度至少为3才有气球可戳）
        for (int size = 2; size < len; size++) {
            for (int i = 0; i + size < len; i++) {
                int j = i + size;
                
                // 枚举区间(i,j)内最后一个被戳破的气球k
                for (int k = i + 1; k < j; k++) {
                    // dp[i][k]: 左半区间(i,k)的最大收益
                    // dp[k][j]: 右半区间(k,j)的最大收益
                    // arr[i]*arr[k]*arr[j]: 最后戳k的收益
                    int coins = dp[i][k] + dp[k][j] + arr[i] * arr[k] * arr[j];
                    dp[i][j] = Math.max(dp[i][j], coins);
                }
            }
        }
        
        return dp[0][n + 1];
    }
}

Mermaid区间DP示意：

四、解法二：记忆化搜索（自顶向下）

/**
 * 312. 戳气球 - 记忆化搜索
 * 逻辑更直观，递推关系更清晰
 */
public int maxCoinsMemo(int[] nums) {
    int n = nums.length;
    int[] arr = new int[n + 2];
    arr[0] = arr[n + 1] = 1;
    for (int i = 0; i < n; i++) arr[i + 1] = nums[i];
    
    int len = n + 2;
    int[][] memo = new int[len][len];
    for (int[] row : memo) Arrays.fill(row, -1);
    
    return dfs(arr, 0, n + 1, memo);
}

/**
 * 返回戳破开区间(i,j)内所有气球的最大收益
 */
private int dfs(int[] arr, int i, int j, int[][] memo) {
    if (j - i < 2) return 0;  // 区间内没有气球
    if (memo[i][j] != -1) return memo[i][j];
    
    int maxCoins = 0;
    // 枚举最后戳的气球k
    for (int k = i + 1; k < j; k++) {
        int coins = dfs(arr, i, k, memo)
                  + dfs(arr, k, j, memo)
                  + arr[i] * arr[k] * arr[j];
        maxCoins = Math.max(maxCoins, coins);
    }
    
    memo[i][j] = maxCoins;
    return maxCoins;
}

五、正向 vs 逆向思维对比

思维角度枚举状态稳定性可行性
正向：枚举第一个第一个戳哪个戳后相邻关系改变，状态不稳定无法定义合理状态
逆向：枚举最后一个最后一个戳哪个边界固定，左右邻居不变完美定义状态

逆向思维的本质：通过考虑"最后一步"，把"已经发生"的事情变成"还没发生"，从而固定住状态边界。这个思路在其他题目里也能用到，比如矩阵链乘（枚举最后一次分割点）。

六、举一反三

区间DP逆向思维的同类题：

  1. LeetCode 1039. 多边形三角剖分的最低得分：枚举三角形最后一条边
  2. LeetCode 87. 扰乱字符串：三维区间DP
  3. 矩阵链乘法：经典区间DP，枚举最后一次矩阵乘法的分割点

通用逆向区间DP框架：

// 枚举"区间内最后处理的那个元素"
for (int size = 2; size < n; size++) {
    for (int i = 0; i + size < n; i++) {
        int j = i + size;
        for (int k = i + 1; k < j; k++) {
            dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + cost(i, k, j));
        }
    }
}

七、踩坑实录

坑一：哨兵的位置和数值

在原数组两端加哨兵1，是为了处理边界气球的"虚拟邻居"。哨兵不参与被戳，只是边界标记。如果忘记加哨兵，会导致数组越界或者错误的收益计算。

坑二：区间是开区间还是闭区间

dp[i][j] 的区间是开区间 (i, j)，i 和 j 本身不被戳。很多人搞混了，把 k 的枚举范围写成 k >= i（包含了边界），导致 i 和 j 会被当作普通气球处理，计算错误。

坑三：遍历顺序写成按端点而非按长度

经典错误，和上一篇一样。for i from 0 to n, for j from i to n 的顺序会导致用到未计算的子区间。必须按 size（区间长度）从小到大枚举。

坑四：索引混淆（扩展数组后）

加了哨兵之后，arr 的长度是 n+2，索引是0到n+1。dp 的大小也应该是 (n+2)×(n+2)。最终答案是 dp[0][n+1]，不是 dp[0][n]。很多人忘记调整 dp 的大小，导致越界或者答案位置读错。

八、总结

戳气球是区间DP里最具代表性的"逆向思维"题：

核心思想：不枚举第一个戳的，枚举最后一个戳的，从而固定两端边界，得到稳定的状态转移。

这道题把区间DP的精髓发挥得淋漓尽致：大问题拆成两个不重叠的子问题，加上当前的决策代价，取所有可能的最优。

时间复杂度 O(n³)，空间复杂度 O(n²)，对于 n≤300 完全可以接受。

编辑此页
最近更新:
贡献者: xiaozhangge