数据结构与算法 / 系统课时
用戳气球理解逆向区间决策
用戳气球理解逆向区间决策
有些区间问题最难的地方不是“算哪个状态”,而是一次操作会改变后续的相邻关系。戳气球就是典型例子:若按第一个被戳的气球递推,边界会不断变化;改为枚举区间里最后被戳的气球,两侧就能彻底分离。
学习目标
- 解释为什么正向枚举“先戳谁”难以形成稳定子问题
- 用“最后一个操作”定义区间状态并写出转移方程
- 实现戳气球的区间 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),所以按区间长度从小到大计算。
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]))预期输出
167以完整区间为例,最优方案并不要求你从左到右模拟真实的戳破顺序。DP 只关心每个区间“最后留下谁”,再把两个更小区间的最优值合并起来。状态表记录的是最优结果,而不是具体操作历史。
复杂度与适用信号
数组长度为 n 时,一共有平方级别的区间状态,每个状态还要枚举一个最后位置,因此时间复杂度是 O(n^3),空间复杂度是 O(n^2)。
这类方法不只适用于戳气球。只要一次操作会改变剩余元素之间的邻接关系,就值得尝试把问题反过来问:能否枚举某个区间最后发生的操作,让它发生时边界已经固定? 如果最后一步能够把区间切成两个互不影响的子问题,通常就能建立区间 DP。