LeetCode 312困难区间 DP
戳气球 图解题解
这道题到底在问什么
有 n 个气球，编号 0 到 n-1，数字存在 nums 中。戳破第 i 个气球可获得 nums[i-1] * nums[i] * nums[i+1] 枚硬币；越界邻居视为数字 1。求戳破所有气球能获得的最大硬币数。
- 输入
- nums = [3,1,5,8]
- 输出
- 167
- 解释
- 一种最优顺序是 1,5,3,8，总硬币数 167。
- 输入
- nums = [1,5]
- 输出
- 10
先想最直接的笨办法
正着想：如果先戳 idx2 的 5（红框），它此刻的左右邻居是 1 和 8。可一旦 5 没了，1 和 8 就塌缩贴到一起，后面谁的邻居是谁全乱了。这就是“正着枚举第一个戳谁”会失控的根源。（动画第 6 步）
最优解：一步一步想明白
- 3这题不能正着模拟所有顺序，必须把“相邻变化”变成稳定边界。
- 4区间 DP 的状态是 dp[left][right]：只戳破 left 和 right 之间的气球，最多能拿多少硬币。
- 5先把 [3,1,5,8] 四个气球真实摆出来。每个气球的收益取决于它左右两个邻居——这正是这题最别扭的地方：戳掉一个，邻居就换人。
- 6正着想：如果先戳 idx2 的 5（红框），它此刻的左右邻居是 1 和 8。可一旦 5 没了，1 和 8 就塌缩贴到一起，后面谁的邻居是谁全乱了。这就是“正着枚举第一个戳谁”会失控的根源。
- 7倒着想：假设 idx2 的 5 是“3 和 8 之间最后一个被戳的”。既然它最后才戳，那 3、8 此刻必然都还没倒（绿框锁死），收益 arr[left]×arr[k]×arr[right]=3×5×8 就被钉死了。这一帧就是 gain 公式的出处——它对上的不是格子里的数字，而是“最后一戳时左右墙还在”这个画面。
- 8arr = [1] + nums + [1]两端补 1 后，arr=[1,3,1,5,8,1]：下标 0 和 5 是补出来的边界 1，中间 1~4 才是原数组。任意区间的左右边界都有固定数字。
- 9length = 2所有长度为 2 的开区间里都只有一个气球，同一轮 length=2 里一并算出、互不依赖、谁先谁后无所谓。后面长区间会依赖这些短区间。
- 10left=0,right=3; for k in (1,2)区间 (0,3) 里有 3 和 1。枚举最后戳哪个，取最大值 30。
- 11left=1,right=4; for k in (2,3)最后戳 5 时，左右边界固定为 3 和 8，收益 3*5*8，再加左区间 dp[1][3]。
- 12left=2,right=5; for k in (3,4)同样枚举最后一个气球，区间答案只依赖已经算过的更短区间。
- 13left=1,right=5; k=2,3,4dp[0][4] 和 dp[1][5] 都是长度 4，同一轮里算，谁先谁后无所谓——这里先把 dp[0][4]=159 算好，纯粹是为了下一步 dp[0][5] 直接引用，不是同长度区间之间有依赖。如果 8 是 (1,5) 里最后被戳的气球，左侧 dp[1][4]=135，再加 3*8*1。
- 14left=0,right=5; k=1..4之前所有算好的格子都还在表里。最后戳 8 时引用左区间 dp[0][4]=159（已高亮）再加 1*8*1=167，这就是 (0,5) 整段的答案。
- 15for length in range(2, n)整张表填完后一目了然：越靠对角线的越短、越先算；代码按区间长度递增填写，保证 dp[left][k] 和 dp[k][right] 已经算好。注意别把两个“方向”搞混：倒着想 = 转移时假设 k 是区间里最后被戳的那个（想问题的视角）；从短到长填 = 计算时按区间长度递增的顺序。一个是想问题的角度，一个是写循环的顺序，不矛盾。
- 16return dp[0][n - 1]整张表都算好了，右上角的 dp[0][5]=167 就是最终答案。虚拟边界不是真气球，只是为了让答案落在 dp[0][n-1]。
- 19戳气球是区间 DP 经典题，难点在建模，不在代码长度。
⚠️ 容易写错的地方
✗ 错：正着枚举第一个戳谁
✓ 对：枚举区间里最后戳谁
第一个戳谁会让邻居变化，最后戳谁边界固定。
✗ 错：忘记补左右 1
✓ 对：arr = [1] + nums + [1]
边界气球的收益需要统一处理。
✗ 错：区间闭区间混用
✓ 对：dp[left][right] 表示开区间
转移里的 k 必须在 left 和 right 之间。
完整代码（Python / C++ / Java）
Python
class Solution:
def maxCoins(self, nums):
arr = [1] + nums + [1]
n = len(arr)
dp = [[0] * n for _ in range(n)]
for length in range(2, n):
for left in range(0, n - length):
right = left + length
for k in range(left + 1, right):
gain = arr[left] * arr[k] * arr[right]
dp[left][right] = max(dp[left][right],
dp[left][k] + gain + dp[k][right])
return dp[0][n - 1]C++
class Solution {
public:
int maxCoins(vector<int>& nums) {
vector<int> arr; arr.push_back(1);
for (int x : nums) arr.push_back(x);
arr.push_back(1);
int n = arr.size();
vector<vector<int>> dp(n, vector<int>(n));
for (int len = 2; len < n; len++) {
for (int left = 0; left + len < n; left++) {
int right = left + len;
for (int k = left + 1; k < right; k++) {
int gain = arr[left] * arr[k] * arr[right];
dp[left][right] = max(dp[left][right], dp[left][k] + gain + dp[k][right]);
}
}
}
return dp[0][n - 1];
}
};Java
class Solution {
public int maxCoins(int[] nums) {
int n = nums.length + 2;
int[] arr = new int[n];
arr[0] = arr[n - 1] = 1;
for (int i = 0; i < nums.length; i++) arr[i + 1] = nums[i];
int[][] dp = new int[n][n];
for (int len = 2; len < n; len++) {
for (int left = 0; left + len < n; left++) {
int right = left + len;
for (int k = left + 1; k < right; k++) {
int gain = arr[left] * arr[k] * arr[right];
dp[left][right] = Math.max(dp[left][right], dp[left][k] + gain + dp[k][right]);
}
}
}
return dp[0][n - 1];
}
}套路模板：区间 DP 可背骨架
# 区间 DP 四步骨架（戳气球套这个模板）
arr = [1] + nums + [1] # 1) 补虚拟边界，让每段都有左右墙
n = len(arr)
dp = [[0] * n for _ in range(n)] # 2) dp[l][r]=开区间(l,r)的最优解
for length in range(2, n): # 3) 先短后长：依赖永远先就绪
for left in range(0, n - length):
right = left + length
for k in range(left + 1, right): # 4) 枚举区间里“最后处理谁”
gain = arr[left] * arr[k] * arr[right] # 最后一步收益，边界固定
dp[left][right] = max(dp[left][right],
dp[left][k] + gain + dp[k][right])
return dp[0][n - 1] # 整段(0,n-1)就是答案// 区间 DP 四步骨架（戳气球套这个模板）
vector<int> arr = {1}; // 1) 补虚拟边界
for (int x : nums) arr.push_back(x);
arr.push_back(1);
int n = arr.size();
vector<vector<int>> dp(n, vector<int>(n)); // 2) dp[l][r]=开区间(l,r)最优解
for (int length = 2; length < n; length++) // 3) 先短后长
for (int left = 0; left + length < n; left++) {
int right = left + length;
for (int k = left + 1; k < right; k++) { // 4) 枚举最后处理谁
int gain = arr[left] * arr[k] * arr[right];
dp[left][right] = max(dp[left][right],
dp[left][k] + gain + dp[k][right]);
}
}
return dp[0][n - 1]; // 整段就是答案// 区间 DP 四步骨架（戳气球套这个模板）
int n = nums.length + 2;
int[] arr = new int[n]; // 1) 补虚拟边界
arr[0] = arr[n - 1] = 1;
for (int i = 0; i < nums.length; i++) arr[i + 1] = nums[i];
int[][] dp = new int[n][n]; // 2) dp[l][r]=开区间(l,r)最优解
for (int length = 2; length < n; length++) // 3) 先短后长
for (int left = 0; left + length < n; left++) {
int right = left + length;
for (int k = left + 1; k < right; k++) { // 4) 枚举最后处理谁
int gain = arr[left] * arr[k] * arr[right];
dp[left][right] = Math.max(dp[left][right],
dp[left][k] + gain + dp[k][right]);
}
}
return dp[0][n - 1]; // 整段就是答案复杂度
时间复杂度
O(n³)
枚举区间长度、左边界和最后戳的 k。
空间复杂度
O(n²)
二维 dp 表保存所有区间答案。
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 戳气球 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
dp[left][right] 表示什么？+
开区间 (left,right) 内所有气球戳完的最大金币。
为什么枚举最后一个？+
最后戳 k 时左右边界固定，收益才能独立计算。
遍历顺序是什么？+
先小区间再大区间，因为大区间依赖左右小区间。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。