HR能看到所有人的工资，那看到一群人比自己多，会不会眼红？

面试时听到“戳气球”这仨字，我第一反应是：这是在考你情绪管理能力吗？🤔你要是能忍住不戳，说明你情商高，要是忍不住，那说明你……得把这道题做出来。

讲真，这道题要真硬刚暴力解法，怕不是直接把CPU烧糊了。因为你要是每次都暴力地模拟戳气球，复杂度是 O(n!)，你敢交，面试官都不敢跑你代码。

咱们先来看看题目：

给你 n 个气球，编号为 0 到 n - 1，每个气球上都写了一个数字。你每次戳破一个气球，可以获得 coins = nums[left] * nums[i] * nums[right] 的金币，然后这个气球就消失，left 和 right 是它旁边还没被戳破的气球。问你戳破所有气球最多能获得多少金币？

我第一反应就是：这不就区间DP的亲儿子吗？👀

这类题的共同点就是：你得反着思考！不是考虑“第一个戳哪个”，而是考虑“最后一个戳哪个”。因为最后戳的时候，左右边界是确定的，这才方便你计算收益。

所以核心思路是：

// dp[i][j] 代表开区间 (i, j) 内可以获得的最大金币数
// 枚举 i < k < j，把 k 当作最后戳的那个气球
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j])

注意，这里 nums 要加哨兵，也就是头尾加个 1，不然边界不好处理：

int[] balloons = newint[n + 2];
balloons[0] = balloons[n + 1] = 1;
System.arraycopy(nums, 0, balloons, 1, n);

上完整代码，不墨迹：

publicintmaxCoins(int[] nums) {
intn= nums.length;
int[] balloons = newint[n + 2];
    balloons[0] = balloons[n + 1] = 1;
    System.arraycopy(nums, 0, balloons, 1, n);

int[][] dp = newint[n + 2][n + 2];

for (intlen=2; len <= n + 1; len++) {
for (intleft=0; left <= n + 1 - len; left++) {
intright= left + len;
for (intk= left + 1; k < right; k++) {
                dp[left][right] = Math.max(dp[left][right],
                    dp[left][k] + dp[k][right] + balloons[left] * balloons[k] * balloons[right]);
            }
        }
    }

return dp[0][n + 1];
}

这题写完，我就有种劫后余生的感觉。你说平时戳气球图个乐子，这题戳完气球图个秃头。🤯

顺带一提，这题跟“合并石子”、“矩阵链乘”、“回文串分割”都是一家子的，一种“我不告诉你从哪分，但你得自己琢磨出怎么分”的思维模式。遇到就一个字：分！（不是分手的分）

我觉得区间DP的本质是给你一个线性结构，让你自己决定在哪儿“断刀下手”，而戳气球这个题的精髓就在于：你不能正着想，要反着来，想谁最后戳。就像日常写代码，很多时候不是你“第一个类怎么设计”，而是你“最后要暴露什么接口”，得从终点开始逆推。

至于“为什么不能先戳哪个”的思路行不通？那就像早恋，虽然你一开始热情高涨，但中途一出bug，最后连接口都调不通，你只能被迫分手重构（说多了都是泪 😅）。

所以，这题的正确打开方式是：加哨兵 + 区间DP + 反向思考。效率稳稳地 O(n³)，虽然不快，但够用了。

话说回来，我有一次面试时被问到这题，脑袋一热差点写了个回溯😂，还好临门一脚想起了“最后戳”的思路，不然可能连“你再考虑考虑”这句话都听不到。

兄弟们，下次再有人跟你说“你戳我试试”，你可得警觉点，也许是要考你区间DP了！