题目描述
思路解析动画文字版
这题不能正着模拟所有顺序，必须把“相邻变化”变成稳定边界。
区间 DP 的状态是 dp[left][right]：只戳破 left 和 right 之间的气球，最多能拿多少硬币。
灵魂帧①：四个气球摆上台：先把 [3,1,5,8] 四个气球真实摆出来。每个气球的收益取决于它左右两个邻居——这正是这题最别扭的地方：戳掉一个，邻居就换人。
灵魂帧②：正着戳，邻居会乱跑：正着想：如果先戳 idx2 的 5（红框），它此刻的左右邻居是 1 和 8。可一旦 5 没了，1 和 8 就塌缩贴到一起，后面谁的邻居是谁全乱了。这就是“正着枚举第一个戳谁”会失控的根源。
灵魂帧③：倒着想，边界就钉死了：倒着想：假设 idx2 的 5 是“3 和 8 之间最后一个被戳的”。既然它最后才戳，那 3、8 此刻必然都还没倒（绿框锁死），收益 arr[left]×arr[k]×arr[right]=3×5×8 就被钉死了。这一帧就是 gain 公式的出处——它对上的不是格子里的数字，而是“最后一戳时左右墙还在”这个画面。
加虚拟边界：arr = [1,3,1,5,8,1]：两端补 1 后，arr=[1,3,1,5,8,1]：下标 0 和 5 是补出来的边界 1，中间 1~4 才是原数组。任意区间的左右边界都有固定数字。
长度 2：一次填完所有单气球区间：所有长度为 2 的开区间里都只有一个气球，同一轮 length=2 里一并算出、互不依赖、谁先谁后无所谓。后面长区间会依赖这些短区间。
计算 dp[0][3]：最后戳 3 或 1：区间 (0,3) 里有 3 和 1。枚举最后戳哪个，取最大值 30。
计算 dp[1][4]：边界是 3 和 8：最后戳 5 时，左右边界固定为 3 和 8，收益 3*5*8，再加左区间 dp[1][3]。
计算 dp[2][5]：边界是 1 和 1：同样枚举最后一个气球，区间答案只依赖已经算过的更短区间。
计算 dp[1][5]：最后戳 8 最好：dp[0][4] 和 dp[1][5] 都是长度 4，同一轮里算，谁先谁后无所谓——这里先把 dp[0][4]=159 算好，纯粹是为了下一步 dp[0][5] 直接引用，不是同长度区间之间有依赖。如果 8 是 (1,5) 里最后被戳的气球，左侧 dp[1][4]=135，再加 3*8*1。
计算最终 dp[0][5]：之前所有算好的格子都还在表里。最后戳 8 时引用左区间 dp[0][4]=159（已高亮）再加 1*8*1=167，这就是 (0,5) 整段的答案。
循环顺序：先短区间，再长区间：整张表填完后一目了然：越靠对角线的越短、越先算；代码按区间长度递增填写，保证 dp[left][k] 和 dp[k][right] 已经算好。注意别把两个“方向”搞混：倒着想 = 转移时假设 k 是区间里最后被戳的那个（想问题的视角）；从短到长填 = 计算时按区间长度递增的顺序。一个是想问题的角度，一个是写循环的顺序，不矛盾。
返回 dp[0][n-1]：整张表都算好了，右上角的 dp[0][5]=167 就是最终答案。虚拟边界不是真气球，只是为了让答案落在 dp[0][n-1]。
戳气球是区间 DP 经典题，难点在建模，不在代码长度。
边界三连：戳气球 的边界先看最小规模、特殊输入和最容易触发分支的样例。
面试追问：戳气球 的追问重点，是把动画里的状态定义、边界和复杂度讲成自己的话。
参考代码
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]复杂度
- 时间复杂度：O(n³)，枚举区间长度、左边界和最后戳的 k。
- 空间复杂度：O(n²)，二维 dp 表保存所有区间答案。
可套用的代码模板
这是“区间 DP”的通用骨架，不是抄上面的参考代码：补边界 → 定义 dp[l][r] → 长度从小到大 → 枚举区间里最后处理谁。换成石子合并、回文子序列也是这四步，只有 gain 那行随题改。右上角可切 C++ / Java。
# 区间 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[left][right] 表示什么？
追问为什么枚举最后一个？
追问遍历顺序是什么？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
正则表达式匹配
LeetCode 10 · 困难 · 沿着 二维动态规划 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题