Article / 文章
LeetCode 第312题：戳气球
有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。 现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i-1] nums[i] nums[i+1] 枚硬币。这里的 i-1 和 i+1 代表和 i 相邻的两个气球的序号。如果 i-1 或 i+1 超出了数组的边界，那么就当它是一个数字为 1 的
📖 文章摘要
本文详细解析LeetCode第312题“戳气球”，这是一道经典的区间动态规划题目。文章提供了基于区间DP的解决方案，包含C#、Python、C++三种语言实现，配有详细的状态转移分析和性能分析。适合想要提升动态规划能力的程序员。
核心知识点： 区间动态规划、状态转移、分治思想、记忆化搜索
难度等级： 困难
推荐人群： 具有基础动态规划知识，想要挑战高难度算法问题的程序员
题目描述
有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i-1] * nums[i] * nums[i+1] 枚硬币。这里的 i-1 和 i+1 代表和 i 相邻的两个气球的序号。如果 i-1 或 i+1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
求所能获得硬币的最大数量。
示例
示例 1：
输入：nums = [3,1,5,8]
输出：167
解释：
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
戳破气球的顺序可以为 [1,5,3,8]
获得的硬币数为: 3*1*5 + 3*5*8 + 3*8*1 + 8*1*1 = 167示例 2：
输入：nums = [1,5]
输出：10提示
- n == nums.length
- 1 <= n <= 500
- 0 <= nums[i] <= 100
解题思路
本题的关键是使用区间动态规划，从小区间推导到大区间。
关键点：
- 逆向思维：不是戳破气球，而是最后添加气球
- 区间DP：考虑最后一个添加的气球
- 状态定义：dp[i][j]表示开区间(i,j)能获得的最大硬币数
- 边界处理：添加两个虚拟气球，值为1
具体步骤：
- 添加边界气球，构造新数组
- 定义dp数组，表示区间最大值
- 从小区间到大区间进行状态转移
- 考虑区间内最后添加的气球
- 返回整个区间的最大值
图解思路
动态规划状态分析表
| 状态 | 含义 | 转移方程 | 说明 |
|---|---|---|---|
| dp[i][j] | (i,j)区间最大值 | max(dp[i][k] + dp[k][j] + val[i]*val[k]*val[j]) | k为最后添加的气球 |
| 初始状态 | dp[i][i+1] = 0 | - | 相邻位置无法获得硬币 |
| 最终结果 | dp[0][n+1] | - | 整个区间的最大值 |
区间转移分析表
| 区间长度 | 计算方式 | 依赖关系 | 说明 |
|---|---|---|---|
| 2 | 直接计算 | 无 | 基础情况 |
| 3 | 一次分割 | 长度为2 | 单个气球 |
| >3 | 多次分割 | 更小区间 | 多个气球 |
代码实现
C# 实现
public class Solution {
public int MaxCoins(int[] nums) {
int n = nums.Length;
int[] val = new int[n + 2];
val[0] = val[n + 1] = 1;
for (int i = 0; i < n; i++) {
val[i + 1] = nums[i];
}
int[,] dp = new int[n + 2, n + 2];
// 从小区间到大区间
for (int len = 3; len <= n + 2; len++) {
for (int i = 0; i <= n + 2 - len; i++) {
int j = i + len - 1;
for (int k = i + 1; k < j; k++) {
dp[i,j] = Math.Max(dp[i,j],
dp[i,k] + dp[k,j] + val[i] * val[k] * val[j]);
}
}
}
return dp[0,n + 1];
}
}Python 实现
class Solution:
def maxCoins(self, nums: List[int]) -> int:
n = len(nums)
val = [1] + nums + [1]
@lru_cache(None)
def solve(i: int, j: int) -> int:
if i >= j - 1:
return 0
best = 0
for k in range(i + 1, j):
total = val[i] * val[k] * val[j]
total += solve(i, k) + solve(k, j)
best = max(best, total)
return best
return solve(0, n + 1)C++ 实现
class Solution {
public:
int maxCoins(vector<int>& nums) {
int n = nums.size();
vector<int> val(n + 2);
val[0] = val[n + 1] = 1;
for (int i = 0; i < n; i++) {
val[i + 1] = nums[i];
}
vector<vector<int>> dp(n + 2, vector<int>(n + 2));
for (int len = 3; len <= n + 2; len++) {
for (int i = 0; i <= n + 2 - len; i++) {
int j = i + len - 1;
for (int k = i + 1; k < j; k++) {
dp[i][j] = max(dp[i][j],
dp[i][k] + dp[k][j] + val[i] * val[k] * val[j]);
}
}
}
return dp[0][n + 1];
}
};执行结果
C# 实现
- 执行用时：84 ms
- 内存消耗：35.8 MB
Python 实现
- 执行用时：228 ms
- 内存消耗：16.4 MB
C++ 实现
- 执行用时：8 ms
- 内存消耗：8.6 MB
性能对比
| 语言 | 执行用时 | 内存消耗 | 特点 |
|---|---|---|---|
| C# | 84 ms | 35.8 MB | 性能适中，内存占用较大 |
| Python | 228 ms | 16.4 MB | 执行较慢，内存占用适中 |
| C++ | 8 ms | 8.6 MB | 执行最快，内存占用最小 |
代码亮点
- 🎯 巧妙使用区间DP解决复杂问题
- 💡 Python实现中使用@lru_cache优化递归
- 🔍 边界处理技巧（添加虚拟气球）
- 🎨 代码结构清晰，变量命名直观
常见错误分析
- 🚫 未正确处理边界情况
- 🚫 区间遍历顺序错误
- 🚫 状态转移方程写错
- 🚫 未考虑所有可能的分割点
解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 贪心 | O(n) | O(1) | 简单快速 | 结果错误 |
| 记忆化搜索 | O(n³) | O(n²) | 容易理解 | 递归开销 |
| 区间DP | O(n³) | O(n²) | 效率稳定 | 空间消耗大 |
相关题目
📖 系列导航
🔥 算法专题合集 - 查看完整合集
📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第312题。
💬 互动交流
感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。
如果这篇文章对你有帮助，请：
- 👍 点个赞，让更多人看到这篇文章
- 📁 收藏文章，方便后续查阅复习
- 🔔 关注作者，获取更多高质量算法题解
- 💭 评论区留言，分享你的解题思路或提出疑问
你的支持是我持续分享的动力！
💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！