312. 戳气球
题目描述
有 n 个气球，编号为 0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。戳破第 i 个气球，可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。这里 nums[-1] 和 nums[n] 都视为 1。
求所能获得硬币的最大数量。
示例
示例 1：
输入：nums = [3,1,5,8]
输出：167
解释：
nums = [3,1,5,8] -> [3,5,8] -> [3,8] -> [8] -> []
coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 15 + 120 + 24 + 8 = 167
示例 2：
输入：nums = [1,5]
输出：10
解题思路
第一步：理解问题本质
戳破气球的顺序会影响最终收益。关键问题是：按什么顺序戳破气球能获得最多硬币？
第二步：为什么正向思考困难
如果正向思考（先戳哪个气球），会发现戳破一个气球后，周围的边界会发生变化，状态很复杂。
核心转换：反过来想，考虑最后一个被戳破的气球。
第三步：逆向思维——区间DP
关键洞察：
- 在数组两端添加虚拟气球
1，这样每个真实气球被戳破时，左右边界都确定了 dp[i][j]表示戳破(i,j)开区间内所有气球能获得的最大硬币数- 枚举
k为(i,j)区间内最后一个被戳破的气球
状态转移：
dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j])，其中 i < k < j
为什么正确：
- 最后一个被戳破的
k，其左右(i,k)和(k,j)的气球已经被戳破 - 此时戳破
k获得的硬币 =nums[i] * nums[k] * nums[j] - 左右子问题互相独立，用加法原理
完整代码实现
from typing import List
class Solution:
"""
戳气球 - 区间动态规划
dp[i][j] 表示戳破 (i,j) 开区间内所有气球能获得的最大硬币数
在数组两端添加虚拟气球1，简化边界处理
时间复杂度：O(n^3)
空间复杂度：O(n^2)
"""
def maxCoins(self, nums: List[int]) -> int:
# 在数组两端添加虚拟气球1
nums = [1] + nums + [1]
n = len(nums)
# dp[i][j] 表示戳破 (i,j) 开区间内所有气球能获得的最大硬币数
dp = [[0] * n for _ in range(n)]
# 按区间长度从小到大枚举（长度至少为2才有中间元素）
for length in range(2, n):
for i in range(n - length):
j = i + length
# 枚举 (i,j) 区间内最后一个被戳破的气球 k
for k in range(i + 1, j):
dp[i][j] = max(
dp[i][j],
dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]
)
return dp[0][n - 1]
示例推演
以 nums = [3,1,5,8] 为例：
添加虚拟气球：[1, 3, 1, 5, 8, 1]，n=6
区间长度为2（相邻两个虚拟气球之间只有一个真实气球）：
| (i,j) | k | dp[i][k] | dp[k][j] | nums[i]*nums[k]*nums[j] | dp[i][j] |
|---|---|---|---|---|---|
| (0,2) | 1 | 0 | 0 | 131=3 | 3 |
| (1,3) | 2 | 0 | 0 | 315=15 | 15 |
| (2,4) | 3 | 0 | 0 | 158=40 | 40 |
| (3,5) | 4 | 0 | 0 | 581=40 | 40 |
区间长度为3：
| (i,j) | k | dp[i][k] | dp[k][j] | 硬币 | 总和 |
|---|---|---|---|---|---|
| (0,3) | 1 | 0 | 15 | 135=15 | 30 |
| (0,3) | 2 | 3 | 0 | 115=5 | 8 |
| (1,4) | 2 | 0 | 40 | 318=24 | 64 |
| (1,4) | 3 | 15 | 0 | 358=120 | 135 |
| (2,5) | 3 | 0 | 40 | 151=5 | 45 |
| (2,5) | 4 | 40 | 0 | 181=8 | 48 |
区间长度为4：
| (i,j) | k | dp[i][k] | dp[k][j] | 硬币 | 总和 |
|---|---|---|---|---|---|
| (0,4) | 1 | 0 | 135 | 138=24 | 159 |
| (0,4) | 2 | 3 | 40 | 118=8 | 51 |
| (0,4) | 3 | 8 | 0 | 158=40 | 48 |
| (1,5) | 2 | 0 | 48 | 311=3 | 51 | | (1,5) | 3 | 15 | 40 | 351=15 | 70 | | (1,5) | 4 | 135 | 0 | 381=24 | 159 |
区间长度为5（最终结果）：
| (i,j) | k | dp[i][k] | dp[k][j] | 硬币 | 总和 |
|---|---|---|---|---|---|
| (0,5) | 1 | 0 | 159 | 131=3 | 162 |
| (0,5) | 2 | 3 | 48 | 111=1 | 52 |
| (0,5) | 3 | 8 | 40 | 151=5 | 53 |
| (0,5) | 4 | 159 | 0 | 181=8 | 167 |
最终 dp[0][5] = 167。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 暴力枚举 | O(n!) | O(n) | 枚举所有戳破顺序 |
| 区间DP（最优） | O(n^3) | O(n^2) | 枚举区间和分割点 |
易错点总结
1. 为什么枚举最后一个被戳破的气球
正向思考：先戳破一个气球，边界变化，状态复杂。
逆向思考：假设 k 是最后一个被戳破的，那么 k 的左右两边已经被戳破，边界固定为 nums[i] 和 nums[j]。
2. 区间是开区间
dp[i][j] 表示 (i,j) 开区间，即 i 和 j 本身不戳破。这样 k 的范围是 i+1 到 j-1。
3. 虚拟气球
在两端添加 1，这样第一个和最后一个真实气球被戳破时也有确定的左右边界。
扩展思考
1. 空间优化
可以优化到 O(n)，但代码会更复杂。
2. 与矩阵链乘法的关系
本题是区间DP的经典应用，与矩阵链乘法问题结构类似。