题目描述
思路解析
一句话答案：LeetCode 312 戳气球的标准解法是区间 DP：把「先戳谁」倒过来想成「谁最后戳」——区间里最后被戳的气球，左右一定紧贴区间边界，这一戳的硬币是定值，左右两半互不干扰，问题才能拆成独立子问题。两端补 1 后按区间长度从短到长填表，时间 O(n³)、空间 O(n²)。
戳气球这道题真正难在哪
题目给一排气球 nums，戳爆第 i 个能拿 nums[左邻] × nums[i] × nums[右邻] 枚硬币，戳爆之后它的左右两个邻居会接续相邻；数组两端越界的位置按值为 1 的气球算。求把气球全部戳完，最多能拿多少硬币。难点在于：每戳一个气球，剩下气球的邻居关系就变了，同一个气球在不同的戳法顺序里得分完全不同——顺序影响收益。
为什么枚举「先戳谁」的思路走不通
最直觉的想法是递归枚举第一个戳谁：戳掉它，剩下的气球接成新的一排，再对新排递归。但这条路有两个致命伤。其一，戳法顺序有 n! 种，纯枚举指数爆炸。其二，更本质的是子问题没法复用：先戳掉一个气球后，它两侧的气球变成邻居，后续每一步的得分都依赖你之前戳了谁，拆不出独立的子问题，动态规划无从下手。
症结在于先戳的气球会改变局面。那就反着问：有没有哪个决策，做出来之后不影响别人？
为什么倒过来枚举「最后戳谁」就能拆开
关键观察：对一段区间来说，与其想谁先被戳，不如想谁最后被戳。假设开区间 (i, j) 内最后戳爆的是位置 k——戳它的那一刻，区间内其他气球早都没了，k 的左右邻居必然就是边界 i 和 j，所以这一戳的硬币是 nums[i] × nums[k] × nums[j]，一个不依赖任何顺序的定值。
更妙的是，既然 k 最后才被戳，那么在此之前 k 一直立在原地当「隔板」：左半段 (i, k) 里的气球无论怎么戳，右邻居最多碰到 k，绝不会越过去碰到右半段；右半段同理。左右两半彻底解耦，各自独立求最优——这就是区间 DP 的典型思路。
dp 数组为什么定义成开区间、两端为什么补 1
先在原数组两端各补一个 1，得到 a = [1] + nums + [1]，这两个哨兵代表「越界处值为 1 的气球」，且永远不被戳，只当墙用——补了它们，nums[i] × nums[k] × nums[j] 这条公式对边界气球也成立，不用特判。
定义 dp[i][j] 为「戳光开区间 (i, j) 内全部气球能拿的最大硬币」，i、j 本身不戳。转移就是枚举区间内最后戳的位置 k：dp[i][j] = max(dp[i][k] + a[i] × a[k] × a[j] + dp[k][j])，k 取 i+1 到 j-1。填表必须按区间长度从短到长：dp[i][j] 依赖的 dp[i][k] 和 dp[k][j] 都是更短的区间，短的没算好，长的就没依据。答案是 dp[0][n-1]，即戳光整排原始气球；对示例 [3, 1, 5, 8]，这个值是 167。
戳气球的复杂度怎么算，哪里容易翻车
时间 O(n³)：区间 (i, j) 共约 n² 个，每个区间要枚举 O(n) 个候选 k。空间 O(n²)，存整张二维区间表。
两个高频翻车点：一是忘了两端补 1，边界气球的得分公式就会越界或算错；二是填表顺序按普通的行列双重循环来写，会在算长区间时用到还没填的短区间——正确写法是外层循环区间长度 L 从 2 到 n-1，内层再枚举左端点。记住「先戳会缠住、最后戳才独立」，转移方程可以自己推出来。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
关键转念：不去想「先戳谁」，而是想「谁最后戳」。最后戳的那个，左右一定是区间边界，硬币就定死了——这样子问题才不互相缠住。
补边界后行/列都是这 6 个气球（角标:值）。dp[i][j] 只管「i 和 j 之间」那些气球，i、j 本身不戳、只当墙。答案最后落在 dp[0][5]。
区间 (0,2) 里只有 1 个气球（位置 1，值 3）：它就是最后戳的，左右紧贴边界 0、2 → 硬币 = 1×3×1 = 3。
落子：dp[0][2] = 3，最优是「最后戳位置 1（值 3）」那条路。
区间 (1,3) 里只有 1 个气球（位置 2，值 1）：它就是最后戳的，左右紧贴边界 1、3 → 硬币 = 3×1×5 = 15。
落子：dp[1][3] = 15，最优是「最后戳位置 2（值 1）」那条路。
区间 (2,4) 里只有 1 个气球（位置 3，值 5）：它就是最后戳的，左右紧贴边界 2、4 → 硬币 = 1×5×8 = 40。
落子：dp[2][4] = 40，最优是「最后戳位置 3（值 5）」那条路。
区间 (3,5) 里只有 1 个气球（位置 4，值 8）：它就是最后戳的，左右紧贴边界 3、5 → 硬币 = 5×8×1 = 40。
落子：dp[3][5] = 40，最优是「最后戳位置 4（值 8）」那条路。
区间 (0,3) 里枚举「最后戳谁」k=1…2：每个候选 = 左半已戳完 dp[0][k] + 这一戳 1×nums[k]×5 + 右半 dp[k][j]。取最大的那条路。
落子：dp[0][3] = 30，最优是「最后戳位置 1（值 3）」那条路。
区间 (1,4) 里枚举「最后戳谁」k=2…3：每个候选 = 左半已戳完 dp[1][k] + 这一戳 3×nums[k]×8 + 右半 dp[k][j]。取最大的那条路。
落子：dp[1][4] = 135，最优是「最后戳位置 3（值 5）」那条路。
区间 (2,5) 里枚举「最后戳谁」k=3…4：每个候选 = 左半已戳完 dp[2][k] + 这一戳 1×nums[k]×1 + 右半 dp[k][j]。取最大的那条路。
落子：dp[2][5] = 48，最优是「最后戳位置 4（值 8）」那条路。
区间 (0,4) 里枚举「最后戳谁」k=1…3：每个候选 = 左半已戳完 dp[0][k] + 这一戳 1×nums[k]×8 + 右半 dp[k][j]。取最大的那条路。
落子：dp[0][4] = 159，最优是「最后戳位置 1（值 3）」那条路。
区间 (1,5) 里枚举「最后戳谁」k=2…4：每个候选 = 左半已戳完 dp[1][k] + 这一戳 3×nums[k]×1 + 右半 dp[k][j]。取最大的那条路。
落子：dp[1][5] = 159，最优是「最后戳位置 4（值 8）」那条路。
区间 (0,5) 里枚举「最后戳谁」k=1…4：每个候选 = 左半已戳完 dp[0][k] + 这一戳 1×nums[k]×1 + 右半 dp[k][j]。取最大的那条路。
落子：dp[0][5] = 167，最优是「最后戳位置 4（值 8）」那条路。
右上角 dp[0][5] = 167：戳爆全开区间 (0,5)（也就是原始 [3,1,5,8] 全部气球）的最大硬币。两端那两个虚拟 1 永不被戳，只当墙。
边界先想清：单个/两个气球都靠补 1 统一处理。
两个高频追问，答清「最后戳」与「补 1」就拿满分。
参考代码
def maxCoins(nums): a = [1] + nums + [1] n = len(a) dp = [[0]*n for _ in range(n)] for L in range(2, n): # L = j - i for i in range(0, n - L): j = i + L for k in range(i+1, j): v = dp[i][k] + a[i]*a[k]*a[j] + dp[k][j] if v > dp[i][j]: dp[i][j] = v return dp[0][n-1]复杂度
- 时间：O(n³)，n² 个区间，每个枚举 O(n) 个最后戳的 k
- 空间：O(n²)，整张二维区间表
易错点
面试追问把动画讲成自己的话
追问为什么枚举「最后戳」而不是「最先戳」？
追问为什么要在两端补 1？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
正则表达式匹配
LeetCode 10 · 困难 · 沿着 二维动态规划 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题