摘要
“戳气球”这道题听起来挺轻松，但一旦你真的开始写，就会发现它其实是个动态规划中的硬茬。这篇文章我们用 Swift 带你从直觉到推导，再到高效代码实现，一步步吃透这道经典题。并不是所有的气球都能随便戳，有技巧的戳法，才是得分的关键。
描述
给你一个整数数组 nums，每个元素代表一个气球。每次戳破一个气球时，你能获得 nums[i-1] * nums[i] * nums[i+1] 的硬币，左右相邻的气球参与计算，但一旦戳破，那个气球就没了，剩下的就挤到一起了。
举个例子，输入 [3,1,5,8]，最优的戳法是：
戳 1：得 3*1*5 = 15
戳 5：得 3*5*8 = 120
戳 3：得 1*3*8 = 24
戳 8：得 1*8*1 = 8
总计：15+120+24+8 = 167
我们想让这个总和尽可能大。你不能随便从头戳到尾，因为气球位置变化会影响后面的计算，这就是动态规划发力的地方。
题解答案
动态规划要解决两个问题：
- 状态定义：我们定义
dp[i][j]表示在i和j之间（不包含两端）戳气球能获得的最大硬币数。 - 状态转移：我们尝试枚举最后一个戳破的气球
k，那么当前收益是：
dp[i][j] = max(dp[i][j], dp[i][k] + nums[i]*nums[k]*nums[j] + dp[k][j])
注意，这里我们要先在 nums 的两边加上 1，模拟虚拟气球 [1] + nums + [1]，方便处理边界。
题解代码（Swift 实现）
func maxCoins(_ nums: [Int]) -> Int {
let n = nums.count
var points = [1] + nums + [1] // 添加虚拟气球
let len = points.count
var dp = Array(repeating: Array(repeating: 0, count: len), count: len)
for length in 2..<len {
for left in 0..<(len - length) {
let right = left + length
for i in (left + 1)..<right {
dp[left][right] = max(dp[left][right],
dp[left][i] + points[left]*points[i]*points[right] + dp[i][right]
)
}
}
}
return dp[0][len - 1]
}
题解代码分析
来分解一下这段代码到底做了什么：
points = [1] + nums + [1]：给原数组头尾都补个1，方便边界处理，避免越界判断。dp[i][j]：表示区间(i, j)之间（不含 i、j）气球全部戳完能获得的最大金币数。外层
length表示枚举的区间长度，从 2 开始，因为区间长度至少得能容纳一个中间的气球。枚举区间中哪个气球
i最后被戳破，把问题拆成两个子问题：dp[left][i]: 戳(left, i)的部分dp[i][right]: 戳(i, right)的部分- 再加上戳
i自身的分数points[left]*points[i]*points[right]
整个结构是一个经典的区间动态规划套路。
示例测试及结果
来验证一下我们写的函数是否正确：
let nums1 = [3, 1, 5, 8]
print(maxCoins(nums1)) // 输出 167
let nums2 = [1, 5]
print(maxCoins(nums2)) // 输出 10
解释：
- 第一个例子戳法顺序影响很大，但我们用 DP 确保尝试了所有可能；
- 第二个例子，只有两个气球，只能戳一个时同时计算它的左右。
时间复杂度分析
整个三重循环：
- 外层是区间长度，O(n)
- 中间枚举左边界 O(n)
- 内层枚举区间中最后被戳的气球 O(n)
所以整体是 O(n³)，但对于 n <= 300 的数据量，是可以接受的。
空间复杂度分析
我们只用到了一个二维数组 dp[n+2][n+2]，所以空间复杂度为 O(n²)。
总结
“戳气球”这个问题本质上就是一个区间动态规划的经典应用。它教会我们的不仅是技巧，更是：
在不确定顺序、结果与操作关联紧密的场景下，尝试用后序构建 + 区间分治的思维解决问题。
如果你把这类题掌握好了，后面像石子合并、回文子序列、打怪兽之类的复杂区间 DP，基本就没什么可怕的了。