戳气球为什么要用区间 DP？为什么枚举最后一个被戳的气球？

简化版

戳气球适合区间 DP，因为先戳哪个会改变相邻关系，直接枚举第一步很难转移。反过来枚举区间内最后一个被戳的气球 k，此时左右边界还在，收益固定为 nums[left] * nums[k] * nums[right]，再加左右子区间最优值。

详细版

在数组两侧补 1，定义 dp[left][right] 表示戳完开区间 (left,right) 内所有气球能获得的最大硬币数。枚举最后戳的 k，转移为 dp[left][right] = max(dp[left][k] + val[left]*val[k]*val[right] + dp[k][right])。

区间长度从小到大枚举，保证子区间已经计算好。时间复杂度 O(n³)，空间复杂度 O(n²)。这题的面试重点是解释“最后一步”为什么让相邻关系固定。

完整版教学

一、为什么不能自然地枚举第一个戳的气球

如果先戳某个气球，它的左右邻居会立刻变成新邻居，后面收益依赖整个历史顺序。比如 [3,1,5]，先戳 1 和先戳 3，后续数组结构完全不同。

先戳 1: [3, 1, 5] -> [3, 5]
先戳 3: [3, 1, 5] -> [1, 5]

这种“操作改变邻接关系”的题，直接按第一步拆分会让子问题不独立。

二、为什么枚举最后一个气球能拆开区间

反过来想，如果区间 (left,right) 里的气球都要戳完，假设最后戳的是 k。在戳 k 的那一刻，left 和 right 一定还没被戳，因为它们是区间边界。

left  ( 已戳完 )  k  ( 已戳完 )  right

所以最后一步收益固定为：

val[left] * val[k] * val[right]

左右两边分别是独立子区间，这就形成了区间 DP。

记忆钩子：区间 DP 常用技巧是“不问第一步，问最后一步”，最后一步的边界最稳定。

三、状态定义为什么用开区间

定义：

dp[left][right] = 戳完开区间 (left, right) 内所有气球的最大收益

开区间的好处是 left 和 right 不被戳，只作为乘法边界。为了处理原数组边缘，在两侧补 1：

原数组:  [3, 1, 5, 8]
补边界: [1, 3, 1, 5, 8, 1]

最终答案是 dp[0][n+1]，表示戳完两个哨兵之间的所有真实气球。

四、转移公式怎么推出来

枚举 (left,right) 里的最后一个气球 k：

dp[left][right] =
max(
  dp[left][k]
  + val[left] * val[k] * val[right]
  + dp[k][right]
)

部分	含义
`dp[left][k]`	戳完左侧开区间
`val[left]val[k]val[right]`	最后戳 k 的收益
`dp[k][right]`	戳完右侧开区间

左右子区间没有重叠，且最后一步收益不受子区间内部顺序影响。

五、区间长度为什么要从小到大

dp[left][right] 依赖更短的 dp[left][k] 和 dp[k][right]。所以要先计算长度较小的区间，再计算长度较大的区间。

长度 2：区间里 0 个气球，收益 0
长度 3：区间里 1 个气球
长度 4：区间里 2 个气球
...

如果顺序反了，大区间会读取到还没计算的子区间。区间 DP 的循环顺序通常是“枚举长度，再枚举左端点，再枚举分割点”。

六、代码模板

int maxCoins(int[] nums) {
    int n = nums.length;
    int[] val = new int[n + 2];
    val[0] = val[n + 1] = 1;
    for (int i = 0; i < n; i++) val[i + 1] = nums[i];
    int[][] dp = new int[n + 2][n + 2];
    for (int len = 2; len <= n + 1; len++) {
        for (int left = 0; left + len <= n + 1; left++) {
            int right = left + len;
            for (int k = left + 1; k < right; k++) {
                dp[left][right] = Math.max(dp[left][right],
                    dp[left][k] + val[left] * val[k] * val[right] + dp[k][right]);
            }
        }
    }
    return dp[0][n + 1];
}

这里 len 是左右边界距离，k 必须在开区间里，所以范围是 left+1 到 right-1。

七、常见误区与追问

误区：枚举第一个戳的气球。 第一步会改变邻居，子问题边界不固定。
误区：把区间定义成闭区间后边界混乱。 开区间能把左右边界保留下来参与最后一步。
误区：忘记两侧补 1。 原数组边缘气球也需要虚拟邻居。
追问：为什么时间复杂度是 O(n³)？ 区间有 O(n²) 个，每个区间枚举 O(n) 个最后气球。
追问：能不能贪心戳最大收益气球？ 不行，当前收益高可能破坏后续更高组合。
追问：区间 DP 常见信号是什么？ 操作发生在一段区间内，且可以通过枚举分割点拆成左右子问题。

八、加强记忆

戳气球要把思路倒过来：第一步会让邻居乱掉，最后一步会让边界固定。开区间 dp[left][right] 表示戳完中间，枚举最后留下的 k，收益就是左边界、k、右边界三者相乘，再加左右子区间。记住“最后一步固定边界”，区间 DP 的门就打开了。

简化版

详细版