312. 戳气球

发表于 分类于 阅读次数： Waline： 本文字数： 1.1k 阅读时长 ≈ 4 分钟

考点

  • 区间DP
  • 消消乐

戳气球（Burst Balloons）

—— 区间 DP 中“消消乐”问题的经典建模范式

1. 问题回顾与核心困难

给定一个整数数组 \[ \text{nums} = [x_1, x_2, \dots, x_n] \] 每次可以选择一个气球 \(x_k\) 戳破，并获得分数： \[ \text{score} = (\text{当前左邻}) \times x_k \times (\text{当前右邻}) \] 其中“当前左/右邻”指的是在这一时刻尚未被戳破、且与 \(x_k\) 相邻的气球。

核心困难在于：

  • 戳气球会改变相邻关系；
  • 不同的戳破顺序，会导致完全不同的得分结果；
  • 很难用“第几步戳谁”来进行直接的动态规划。

2. 建模的关键转化：从“第一个戳谁”到“最后一个戳谁”

这是所有消消乐类区间 DP 的核心思想。

2.1 直觉转化

与其思考：

“在当前状态下，先戳哪个气球最好？”

不如反过来思考：

“在某一个固定区间内，最后被戳破的气球是谁？”

原因是：

  • 当一个气球是最后一个被戳破时；
  • 它左右两侧的气球一定已经“固定”为区间的边界；
  • 此时的得分是确定的、不依赖顺序的。

3. 边界统一：在数组两端补 1

为消除边界特判，引入哨兵： \[ \text{arr} = [1, x_1, x_2, \dots, x_n, 1] \] 这样：

  • 即使最左或最右的气球最后被戳；
  • 它的“虚拟邻居”也是 1；
  • 所有情况可以统一建模。

4. 状态定义（区间 DP 的标准形式）

4.1 状态含义

定义二维 DP： \[ f[i][j] = \text{戳破区间 } (i, j) \text{ 内所有气球所能获得的最大分数} \] 注意：

  • 这是一个开区间；
  • 下标 \(i, j\) 本身对应的气球 不戳；
  • 它们只作为边界存在。

4.2 目标答案

戳破所有原始气球，对应： \[ \boxed{f[0][n-1]} \] 其中 \(n\) 是补完哨兵后的数组长度。

5. 状态转移方程（本题的灵魂）

5.1 枚举“最后一个被戳破的气球”

假设在区间 \((i, j)\) 内，最后被戳破的是 \(k\)，其中： \[ i < k < j \] 那么：

  • 区间 \((i, k)\) 已经被完全戳完；
  • 区间 \((k, j)\) 也已经被完全戳完；
  • 此时 \(k\) 的左右邻居只能是 \(i\) 和 \(j\)。

5.2 最后一次戳破的收益

\[ \text{gain} = \text{arr}[i] \times \text{arr}[k] \times \text{arr}[j] \]

5.3 完整转移方程

\[ \boxed{ f[i][j] = \max_{i < k < j} \Big( f[i][k] + f[k][j] + \text{arr}[i] \cdot \text{arr}[k] \cdot \text{arr}[j] \Big) } \]

6. 文本示意图：为什么“最后一个”能固定邻居

设当前考虑区间 (i, j)：

1
2
3
4
5
arr[i]   ...   arr[k]   ...   arr[j]
   |            ↑             |
   |        最后被戳          |
   +--------------------------+
          当前处理的区间

当 k 是最后一个被戳时：

  • (i, k) 和 (k, j) 内的气球已经全部消失；
  • k 的左右只能剩下 i 和 j；
  • 得分与顺序无关，只与边界有关。

这正是区间 DP 能成立的根本原因。

7. 初始化与遍历顺序

7.1 初始状态

当区间长度小于 2（即没有气球可戳）： \[ f[i][i+1] = 0 \]

7.2 遍历顺序

  • 按区间长度 len 从小到大枚举；
  • 保证转移所需的子区间已经计算完成。

8. 时间与空间复杂度

  • 状态数：\(O(n^2)\)
  • 每个状态枚举 \(k\)：\(O(n)\)
  • 总时间复杂度：\(\boxed{O(n^3)}\)
  • 空间复杂度：\(\boxed{O(n^2)}\)

9. AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    int maxCoins(vector<int>& nums) {
        // f[i][j]: 戳破 (i, j) 开区间内所有气球的最大得分
        int f[305][305] = {};

        // arr: 原数组两端补 1 之后的结果
        int arr[305];
        int n = 0;

        // 左哨兵
        arr[n++] = 1;

        // 原始气球
        for (int x : nums)
            arr[n++] = x;

        // 右哨兵
        arr[n++] = 1;

        // len 表示区间长度 j - i + 1
        // 至少为 3，才能保证 (i, j) 中间有气球
        for (int len = 3; len <= n; ++len) {
            // j 是右端点
            for (int j = len - 1; j < n; ++j) {
                int i = j - len + 1;

                int mx = -1;

                // arr[i] 和 arr[j] 在本区间内是固定边界
                int mul = arr[i] * arr[j];

                // 枚举最后一个被戳破的气球 k
                for (int k = i + 1; k < j; ++k) {
                    // f[i][k]   : 左子区间
                    // f[k][j]   : 右子区间
                    // mul*arr[k]: 最后戳 k 的收益
                    mx = max(mx, mul * arr[k] + f[i][k] + f[k][j]);
                }

                f[i][j] = mx;
            }
        }

        // 戳破所有原始气球
        return f[0][n - 1];
    }
};

10. 模板总结

当一次操作的收益取决于“当前左右邻居”，并且删除顺序会改变邻居关系时，应考虑区间 DP，枚举“最后一次操作”，把动态邻居转化为静态边界。