题目描述
有 n 个气球，编号为 0 到 n - 1，每个气球上都有一个数字，这些数字存放在数组 nums 中。
现在要求你戳破所有气球。 戳破第 i 个气球时，可以获得的硬币数为：
nums[left] * nums[i] * nums[right]
其中：
-
left和right表示第i个气球左右两边还没有被戳破的气球 -
如果
i左边或右边已经没有气球了，就把它看成数字1
要求返回：戳破所有气球后，最多能获得多少硬币。
示例分析
示例 1
输入: nums = [3,1,5,8]
输出: 167
一种最优戳法可以得到：
167
虽然这题表面上看只是“决定先戳哪个气球”，但真正的难点在于：
某个气球被戳破时，它左右相邻的是谁，会随着前面操作不断变化。
所以这题不能简单贪心。
示例 2
输入: nums = [1,5]
输出: 10
因为：
-
先戳
1，得1 * 1 * 5 = 5 -
再戳
5，得1 * 5 * 1 = 5
总和为：
10
解题思路
这道题是一道非常经典的区间 DP题。
很多同学第一次做这题时，最自然的想法是：
先决定“第一个戳哪个气球”。
但这样会非常难处理。
因为如果你先戳掉某个气球，那么后面的左右边界会发生变化，子问题之间很难独立。
所以这题真正的突破口是：
不要想第一个戳哪个，而是想最后一个戳哪个。
这就是整道题最核心的思维转换。
你给出的代码正是这道题最经典的区间 DP 写法。
代码
class Solution {
public int maxCoins(int[] nums) {
int n = nums.length;
int[] arr = new int[n + 2];
arr[0] = arr[n + 1] = 1;
for (int i = 1; i <= n; i++) arr[i] = nums[i - 1];
int[][] f = new int[n + 2][n + 2];
for (int len = 3; len <= n + 2; len++) {
for (int l = 0; l + len - 1 <= n + 1; l++) {
int r = l + len - 1;
for (int k = l + 1; k <= r - 1; k++) {
f[l][r] = Math.max(f[l][r], f[l][k] + f[k][r] + arr[l] * arr[k] * arr[r]);
}
}
}
return f[0][n + 1];
}
}
为什么要反过来想“最后一个戳破的气球”
这是整道题最关键的一点。
假设我们考虑一个开区间：
(l, r)
表示只去戳掉 l 和 r 之间的那些气球，l 和 r 本身暂时不动。
如果我们现在决定：
在
(l, r)这个区间里，最后一个被戳掉的气球是k
那么会发生什么？
因为 k 是最后一个被戳的，所以在戳 k 的那一刻：
-
k左边的区间(l, k)一定已经全部戳完了 -
k右边的区间(k, r)也一定已经全部戳完了 -
所以此时
k左右还剩下的邻居，恰好就是l和r
于是，最后戳 k 所获得的硬币数就确定了：
arr[l] * arr[k] * arr[r]
这就是为什么“最后一个戳哪个”会变得很好算。
而且更重要的是：
-
左边
(l, k)的最优收益 -
右边
(k, r)的最优收益
都变成了彼此独立的子问题。
这就很适合做动态规划。
为什么要在两端补 1
代码里先构造了一个新数组：
int[] arr = new int[n + 2];
arr[0] = arr[n + 1] = 1;
for (int i = 1; i <= n; i++) arr[i] = nums[i - 1];
这一步非常常见，也非常重要。
原因是题目规定：
-
如果某个气球左边没有气球了，就把左边看成
1 -
如果右边没有气球了，就把右边也看成
1
为了统一边界处理，我们直接在原数组两端各补一个 1。
这样：
-
原来的
nums[0]变成arr[1] -
原来的
nums[n - 1]变成arr[n] -
arr[0]和arr[n + 1]就是两个虚拟边界
这样后面写区间 DP 时，不管区间在数组什么位置，公式都统一，不需要单独分类讨论边界情况。
状态定义
我们定义：
f[l][r]
表示：
只戳破开区间
(l, r)内的所有气球，能够获得的最大硬币数。
注意这里是开区间，也就是说：
-
l和r这两个位置的气球不戳 -
只处理中间那些位置
这点非常关键。
例如：
f[0][n + 1]
就表示：
-
两个边界
0和n + 1不动 -
把中间原数组所有气球全部戳完
这正好就是整道题的答案。
状态转移方程
如果在区间 (l, r) 中，最后一个被戳掉的气球是 k，那么：
-
先戳完
(l, k)里的所有气球，收益是f[l][k] -
再戳完
(k, r)里的所有气球，收益是f[k][r] -
最后戳
k，收益是arr[l] * arr[k] * arr[r]
所以总收益就是：
f[l][k] + f[k][r] + arr[l] * arr[k] * arr[r]
枚举所有可能的 k，取最大值：
f[l][r] = max(f[l][k] + f[k][r] + arr[l] * arr[k] * arr[r])
其中：
l < k < r
这就是整道题最核心的区间 DP 转移方程。
代码解析
1. 构造补边界的新数组
int n = nums.length;
int[] arr = new int[n + 2];
arr[0] = arr[n + 1] = 1;
for (int i = 1; i <= n; i++) arr[i] = nums[i - 1];
把原数组复制到中间，并在左右各补一个 1。
例如：
nums = [3,1,5,8]
会变成：
arr = [1,3,1,5,8,1]
2. 定义 DP 数组
int[][] f = new int[n + 2][n + 2];
f[l][r] 表示戳破开区间 (l, r) 的最大收益。
初始时默认都是 0。
为什么初始可以为 0？
因为当区间里没有气球可戳时，收益自然就是 0。
3. 按区间长度从小到大枚举
for (int len = 3; len <= n + 2; len++) {
这里为什么从 3 开始？
因为：
-
区间
(l, r)中至少要有一个气球可戳 -
也就是说，
l和r之间至少要有一个位置k -
所以区间总长度至少要是 3
例如：
[l, k, r]
这是最小可转移区间。
4. 枚举左端点
for (int l = 0; l + len - 1 <= n + 1; l++) {
int r = l + len - 1;
根据左端点和长度，计算右端点。
这样就枚举了所有长度为 len 的区间。
5. 枚举最后一个被戳的气球 k
for (int k = l + 1; k <= r - 1; k++) {
f[l][r] = Math.max(f[l][r], f[l][k] + f[k][r] + arr[l] * arr[k] * arr[r]);
}
这里的 k 就表示：
在区间
(l, r)中最后一个被戳掉的气球
然后根据状态转移公式更新 f[l][r]。
6. 返回答案
return f[0][n + 1];
表示戳掉整个原数组对应的所有气球，得到的最大收益。
示例推演
我们用：
nums = [3,1,5,8]
补边界后：
arr = [1,3,1,5,8,1]
最终要求的是：
f[0][5]
也就是戳掉 (0,5) 中的所有气球。
先看小区间
比如区间：
(1,3)
中间只有一个气球 2 位置上的 1。
那么：
f[1][3] = arr[1] * arr[2] * arr[3]
= 3 * 1 * 5
= 15
再看更大区间
比如区间：
(1,4)
中间有两个气球：
-
2位置 -
3位置
那么最后一个戳的气球有两种选择：
如果最后戳 2
f[1][2] + f[2][4] + arr[1] * arr[2] * arr[4]
如果最后戳 3
f[1][3] + f[3][4] + arr[1] * arr[3] * arr[4]
取两者最大值。
这就是区间 DP 的标准思路。
为什么这题不能贪心
很多同学第一次看到这题时，可能会想：
-
先戳数值小的？
-
先戳收益大的？
-
先戳某个局部最优位置？
这些贪心策略都不靠谱。
因为某个气球被戳时的收益，取决于它当时左右还剩下谁。 而左右是谁，又取决于前面戳掉了哪些气球。
也就是说：
当前决策会影响未来收益，未来操作也会反过来改变当前的价值判断。
所以这题不能简单贪心，必须用动态规划来考虑全局最优。
为什么这是区间 DP
这道题之所以是区间 DP，是因为：
-
我们定义的是一个区间
(l, r)的最优解 -
转移时要枚举区间里某个位置
k作为最后决策点 -
然后问题拆成左右两个更小区间
这正是区间 DP 的典型特征。
类似的经典题还有：
-
石子合并
-
矩阵连乘
-
回文区间类 DP
-
戳气球
所以这题是非常标准、非常有代表性的区间 DP 模板题。
复杂度分析
设原数组长度为 n。
时间复杂度
我们有三层循环：
-
枚举区间长度
-
枚举左端点
-
枚举最后一个气球
k
所以总时间复杂度是：
O(n^3)
空间复杂度
DP 数组大小为：
(n + 2) * (n + 2)
所以空间复杂度是：
O(n^2)
这道题为什么难
这道题难点主要有两个：
1. 想不到“最后一个戳”的思路
如果一直想着“第一个戳哪个”，子问题就会互相影响，很难做。
而一旦反过来想“最后一个戳哪个”，问题立刻就独立了。
2. 开区间状态不太直观
很多人第一次看：
f[l][r] 表示戳掉 (l, r)
会觉得有点抽象。
但其实这是为了保证：
-
l和r始终作为最后戳k时的左右边界存在 -
这样转移公式才统一、漂亮
只要接受了“开区间 + 最后一个戳”的设计，这题就顺了。
总结
这道题的核心可以概括成一句话：
不要想第一个戳哪个，要想最后一个戳哪个。
因为一旦某个气球 k 是区间 (l, r) 中最后一个被戳掉的，那么它的左右邻居就固定是 l 和 r，收益也就确定了。
于是状态转移就变成：
f[l][r] = max(f[l][k] + f[k][r] + arr[l] * arr[k] * arr[r])
你可以把这题记成一句话：
戳气球的本质是区间 DP：枚举区间内最后一个被戳掉的气球。
把这题吃透之后，你对“为什么区间 DP 常常要倒着想”会有更深的理解。
