数据结构与算法 / 系统课时

用戳气球理解逆向区间决策

用戳气球理解逆向区间决策

有些区间问题最难的地方不是“算哪个状态”,而是一次操作会改变后续的相邻关系。戳气球就是典型例子:若按第一个被戳的气球递推,边界会不断变化;改为枚举区间里最后被戳的气球,两侧就能彻底分离。

学习目标

  • 解释为什么正向枚举“先戳谁”难以形成稳定子问题
  • 用“最后一个操作”定义区间状态并写出转移方程
  • 实现戳气球的区间 DP,并分析时间与空间复杂度

为什么先戳谁很难递推

设气球分数为 [3,1,5,8]。戳破位置 i 时得到“当前左邻居 × 当前值 × 当前右邻居”的分数。问题在于,当前邻居取决于此前已经戳掉了哪些气球。

如果第一步戳 1,原本不相邻的 3 和 5 会立刻成为邻居;如果第一步戳 5,则 1 和 8 成为邻居。于是“解决左半段”和“解决右半段”并不是两个独立问题,它们会通过新的相邻关系互相影响。

真正需要改变的不是公式,而是决策顺序:不要问“这个区间第一个戳谁”,而要问“这个区间最后戳谁”。

戳气球从正向耦合到逆向独立的区间决策

用最后一次操作切开区间

先在原数组两端补上值为 1 的虚拟气球。设扩展后的数组为 nums,定义 dp[l][r] 表示:只戳开区间 (l,r) 内的气球,能够获得的最大分数。l 和 r 自身不被戳,它们始终充当这一段的固定边界。

现在枚举 k 为 (l,r) 中最后一个被戳的气球。当 k 被戳时,区间内其他气球都已经消失,所以它此时的左右邻居必然是 l 和 r。最后一步的收益因此稳定为 nums[l] * nums[k] * nums[r]。

在最后一步之前,左侧 (l,k) 和右侧 (k,r) 已经分别处理完,二者互不影响,因此有:

dp[l][r] = max(dp[l][k] + nums[l] * nums[k] * nums[r] + dp[k][r])

这就是“逆向决策”的关键:最后一步把原本动态变化的邻居固定成了区间边界,同时让左右两侧成为独立子问题。

按区间长度完成递推

下面用 Python 实现。因为 dp[l][r] 依赖更短的 (l,k) 和 (k,r),所以按区间长度从小到大计算。

python
def max_coins(balloons):
    nums = [1] + balloons + [1]
    n = len(nums)
    dp = [[0] * n for _ in range(n)]

    # gap 是左右边界的距离;至少相隔 2 才有可戳气球。
    for gap in range(2, n):
        for left in range(0, n - gap):
            right = left + gap
            best = 0
            for last in range(left + 1, right):
                score = (
                    dp[left][last]
                    + nums[left] * nums[last] * nums[right]
                    + dp[last][right]
                )
                best = max(best, score)
            dp[left][right] = best

    return dp[0][n - 1]


if __name__ == '__main__':
    print(max_coins([3, 1, 5, 8]))

预期输出

text
167

以完整区间为例,最优方案并不要求你从左到右模拟真实的戳破顺序。DP 只关心每个区间“最后留下谁”,再把两个更小区间的最优值合并起来。状态表记录的是最优结果,而不是具体操作历史。

复杂度与适用信号

数组长度为 n 时,一共有平方级别的区间状态,每个状态还要枚举一个最后位置,因此时间复杂度是 O(n^3),空间复杂度是 O(n^2)。

这类方法不只适用于戳气球。只要一次操作会改变剩余元素之间的邻接关系,就值得尝试把问题反过来问:能否枚举某个区间最后发生的操作,让它发生时边界已经固定? 如果最后一步能够把区间切成两个互不影响的子问题,通常就能建立区间 DP。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用戳气球理解逆向区间决策

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通