LeetCode 0312 Burst Balloons 完全题解:从暴力递归到区间 DP 的三种解法演进
LeetCode 0312 Burst Balloons 完全题解:从暴力递归到区间 DP 的三种解法演进
导读
本文以 articles/burst-balloons.md 为主体,完整讲解 LeetCode 0312「Burst Balloons(戳气球)」这道经典的区间动态规划(Interval DP)题目。你将掌握三种层层递进的解法:指数级暴力递归、自顶向下记忆化搜索(Top-Down DP)、自底向上填表(Bottom-Up DP),并理解"倒过来思考——每次选择区间内最后被戳破的气球"这一核心洞察。同时结合本仓库(Leetcode solutions)在 python、cpp、java、javascript 等目录下的真实源码与 hints/burst-balloons.md 提示,帮你彻底吃透该题并规避常见误区。
1. 前置知识准备
在着手解决本问题之前,你需要先熟练掌握以下四块基础能力(这也是原文档明确列出的 Prerequisites):
- 递归(Recursion)——把大问题拆解为更小的子问题;
- 动态规划(Dynamic Programming)——使用记忆化(Memoization)与填表(Tabulation)两种技术进行优化;
- 区间 DP(Interval DP)——通过枚举所有可能的子区间并合并结果来求解;
- 数组操作(Array Manipulation)——用边界哨兵值填充数组,从而简化边界情况的处理。
本仓库中与区间 DP 同族的问题还有 burst-balloons 之外的 minimum-number-of-arrows-to-burst-balloons.md(贪心经典题,注意二者解法思路完全不同,后者是排序贪心而非 DP)。
2. 问题本质:收益取决于"当前邻居"
题目要求我们在最优爆炸顺序下收集最大金币数。每戳破一个气球,获得的硬币数取决于它当时的左右邻居(越界时按数值 1 处理)。由于戳破一个气球会改变其他气球的邻居,爆炸顺序对最终收益影响极大。
从仓库源码注释可以印证这一点,cpp/0312-burst-balloons.cpp 顶部注释写道:
"Given array of balloons w/ coins, if burst ith, get (i-1) + i + (i+1) coins. Return max coins can collect by bursting the balloons wisely. DP to return max coins obtainable in each interval [left, right]. Divide & conquer left & right depends on previous bursts, so think backwards. Instead of which one to burst first, need to think which one to burst last."
关键词就是 think backwards(倒过来想) 与 burst last(最后戳破)——这是贯穿全文的灵魂。
3. 解法一:暴力递归(Brute Force)
3.1 直觉(Intuition)
暴力思路:在当前数组中,把每一个气球都当作最后一个被戳破的来尝试:
- 如果选择某个气球现在戳破,收益由它的左右邻居决定;
- 问题随即归约为"戳破剩余气球"的子问题。
递归函数表达的含义是: "从当前这排气球中,我们能收集到的最大硬币数是多少?"
为了简化边界处理,在数组两端各补一个 1,这样每个气球永远都有两个邻居。
3.2 算法步骤
- 在数组开头与结尾各加入一个
1,安全处理边界; - 定义递归函数
dfs(nums):nums表示当前剩余气球列表;
- 若只剩两个边界
1(即没有真实气球):- 返回
0;
- 返回
- 初始化
maxCoins = 0; - 遍历两个边界之间的每个气球下标
i:- 计算戳破
nums[i]所得硬币:nums[i - 1] * nums[i] * nums[i + 1]; - 递归计算剩余气球的最大收益:删除
nums[i]后对新列表调用dfs; - 用最优结果更新
maxCoins;
- 计算戳破
- 返回当前配置的
maxCoins; - 用完整的补边数组启动递归并返回结果。
3.3 多语言实现
Python
class Solution:
def maxCoins(self, nums: List[int]) -> int:
nums = [1] + nums + [1]
def dfs(nums):
if len(nums) == 2:
return 0
maxCoins = 0
for i in range(1, len(nums) - 1):
coins = nums[i - 1] * nums[i] * nums[i + 1]
coins += dfs(nums[:i] + nums[i + 1:])
maxCoins = max(maxCoins, coins)
return maxCoins
return dfs(nums)
Java
public class Solution {
public int maxCoins(int[] nums) {
int[] newNums = new int[nums.length + 2];
newNums[0] = newNums[nums.length + 1] = 1;
for (int i = 0; i < nums.length; i++) {
newNums[i + 1] = nums[i];
}
return dfs(newNums);
}
public int dfs(int[] nums) {
if (nums.length == 2) {
return 0;
}
int maxCoins = 0;
for (int i = 1; i < nums.length - 1; i++) {
int coins = nums[i - 1] * nums[i] * nums[i + 1];
int[] newNums = new int[nums.length - 1];
for (int j = 0, k = 0; j < nums.length; j++) {
if (j != i) {
newNums[k++] = nums[j];
}
}
coins += dfs(newNums);
maxCoins = Math.max(maxCoins, coins);
}
return maxCoins;
}
}
C++
class Solution {
public:
int maxCoins(vector<int>& nums) {
nums.insert(nums.begin(), 1);
nums.push_back(1);
return dfs(nums);
}
int dfs(vector<int>& nums) {
if (nums.size() == 2) return 0;
int maxCoins = 0;
for (int i = 1; i < nums.size() - 1; i++) {
int coins = nums[i - 1] * nums[i] * nums[i + 1];
vector<int> newNums = nums;
newNums.erase(newNums.begin() + i);
coins += dfs(newNums);
maxCoins = max(maxCoins, coins);
}
return maxCoins;
}
};
JavaScript
class Solution {
/**
* @param {number[]} nums
* @return {number}
*/
maxCoins(nums) {
nums.unshift(1);
nums.push(1);
return this.dfs(nums);
}
/**
* @param {number[]} nums
* @return {number}
*/
dfs(nums) {
if (nums.length === 2) return 0;
let maxCoins = 0;
for (let i = 1; i < nums.length - 1; i++) {
let coins = nums[i - 1] * nums[i] * nums[i + 1];
let newNums = nums.slice(0, i).concat(nums.slice(i + 1));
coins += this.dfs(newNums);
maxCoins = Math.max(maxCoins, coins);
}
return maxCoins;
}
}
C#
public class Solution {
public int MaxCoins(int[] nums) {
List<int> newNums = new List<int> {1};
newNums.AddRange(nums);
newNums.Add(1);
return Dfs(newNums);
}
public int Dfs(List<int> nums) {
if (nums.Count == 2) return 0;
int maxCoins = 0;
for (int i = 1; i < nums.Count - 1; i++) {
int coins = nums[i - 1] * nums[i] * nums[i + 1];
List<int> newNums = new List<int>(nums);
newNums.RemoveAt(i);
coins += Dfs(newNums);
maxCoins = Math.Max(maxCoins, coins);
}
return maxCoins;
}
}
Go
func maxCoins(nums []int) int {
nums = append([]int{1}, nums...)
nums = append(nums, 1)
var dfs func(nums []int) int
dfs = func(nums []int) int {
if len(nums) == 2 {
return 0
}
maxCoins := 0
for i := 1; i < len(nums)-1; i++ {
coins := nums[i-1] * nums[i] * nums[i+1]
coins += dfs(append(append([]int{}, nums[:i]...), nums[i+1:]...))
if coins > maxCoins {
maxCoins = coins
}
}
return maxCoins
}
return dfs(nums)
}
Kotlin
class Solution {
fun maxCoins(nums: IntArray): Int {
val newNums = intArrayOf(1) + nums + intArrayOf(1)
fun dfs(nums: IntArray): Int {
if (nums.size == 2) {
return 0
}
var maxCoins = 0
for (i in 1 until nums.size - 1) {
val coins = nums[i - 1] * nums[i] * nums[i + 1]
val nextCoins = dfs(nums.take(i).toIntArray() +
nums.drop(i + 1).toIntArray())
maxCoins = maxOf(maxCoins, coins + nextCoins)
}
return maxCoins
}
return dfs(newNums)
}
}
Swift
class Solution {
func maxCoins(_ nums: [Int]) -> Int {
var nums = [1] + nums + [1]
func dfs(_ nums: [Int]) -> Int {
if nums.count == 2 {
return 0
}
var maxCoins = 0
for i in 1..<(nums.count - 1) {
let coins = nums[i - 1] * nums[i] * nums[i + 1] +
dfs(Array(nums[..<i]) + Array(nums[(i + 1)...]))
maxCoins = max(maxCoins, coins)
}
return maxCoins
}
return dfs(nums)
}
}
Rust
impl Solution {
pub fn max_coins(nums: Vec<i32>) -> i32 {
let mut new_nums = vec![1];
new_nums.extend_from_slice(&nums);
new_nums.push(1);
fn dfs(nums: &Vec<i32>) -> i32 {
if nums.len() == 2 {
return 0;
}
let mut max_coins = 0;
for i in 1..nums.len() - 1 {
let coins = nums[i - 1] * nums[i] * nums[i + 1];
let mut new_nums: Vec<i32> = nums[..i].to_vec();
new_nums.extend_from_slice(&nums[i + 1..]);
let coins = coins + dfs(&new_nums);
max_coins = max_coins.max(coins);
}
max_coins
}
dfs(&new_nums)
}
}
3.4 复杂度分析
- 时间复杂度:——每次递归都要遍历并复制数组,指数爆炸;
- 空间复杂度:——递归调用栈与数组拷贝的开销。
这种解法在 n 稍大(如题目常见的 n ≤ 300)时完全不可行,只适合理解问题结构。
4. 解法二:自顶向下动态规划(记忆化搜索)
4.1 核心洞察:选择"最后一个"而不是"第一个"
暴力递归重复计算了大量相同的子问题。关键在于转换视角:
不要选择区间内第一个戳破的气球,而是选择最后一个戳破的气球。
为什么这样有效:
- 如果气球
i是区间(l..r)内最后一个被戳破的,那么在那一刻:(l..r)内除i之外的所有气球都已消失;i的邻居是固定的:左边是nums[l - 1],右边是nums[r + 1];
- 因此最后戳破
i所得金币为:nums[l - 1] * nums[i] * nums[r + 1]; - 剩下的工作干净地分裂成两个独立子问题:
(l..i-1)内的最优收益;(i+1..r)内的最优收益。
由于存在重叠子问题,我们用备忘录 dp 以 (l, r) 为键缓存结果。
4.2 算法步骤
- 数组两端各加
1,免去边界判断; - 使用备忘录
dp,其中dp[(l, r)]存储区间[l, r]内气球可得到的最大硬币数; - 定义递归函数
dfs(l, r):- 若
l > r,返回0(无气球可戳); - 若
(l, r)已计算过,直接返回缓存值;
- 若
- 枚举区间
[l, r]内的每个气球i作为最后一个被戳破的:- 最后戳破
i的收益:nums[l - 1] * nums[i] * nums[r + 1]; - 加上左侧最优:
dfs(l, i - 1); - 加上右侧最优:
dfs(i + 1, r); - 对所有
i取最大值;
- 最后戳破
- 将最优值存入
dp[(l, r)]并返回; - 最终答案为
dfs(1, len(nums) - 2)(即原始气球区间,排除补上的边界)。
4.3 多语言实现
Python
class Solution:
def maxCoins(self, nums: List[int]) -> int:
nums = [1] + nums + [1]
dp = {}
def dfs(l, r):
if l > r:
return 0
if (l, r) in dp:
return dp[(l, r)]
dp[(l, r)] = 0
for i in range(l, r + 1):
coins = nums[l - 1] * nums[i] * nums[r + 1]
coins += dfs(l, i - 1) + dfs(i + 1, r)
dp[(l, r)] = max(dp[(l, r)], coins)
return dp[(l, r)]
return dfs(1, len(nums) - 2)
Java
public class Solution {
public int maxCoins(int[] nums) {
int n = nums.length;
int[] newNums = new int[n + 2];
newNums[0] = newNums[n + 1] = 1;
for (int i = 0; i < n; i++) {
newNums[i + 1] = nums[i];
}
int[][] dp = new int[n + 2][n + 2];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
dp[i][j] = -1;
}
}
return dfs(newNums, 1, newNums.length - 2, dp);
}
public int dfs(int[] nums, int l, int r, int[][] dp) {
if (l > r) {
return 0;
}
if (dp[l][r] != -1) {
return dp[l][r];
}
dp[l][r] = 0;
for (int i = l; i <= r; i++) {
int coins = nums[l - 1] * nums[i] * nums[r + 1];
coins += dfs(nums, l, i - 1, dp) + dfs(nums, i + 1, r, dp);
dp[l][r] = Math.max(dp[l][r], coins);
}
return dp[l][r];
}
}
C++
class Solution {
public:
int maxCoins(vector<int>& nums) {
int n = nums.size();
vector<int> newNums(n + 2, 1);
for (int i = 0; i < n; i++) {
newNums[i + 1] = nums[i];
}
vector<vector<int>> dp(n + 2, vector<int>(n + 2, -1));
return dfs(newNums, 1, newNums.size() - 2, dp);
}
int dfs(vector<int>& nums, int l, int r, vector<vector<int>>& dp) {
if (l > r) return 0;
if (dp[l][r] != -1) return dp[l][r];
dp[l][r] = 0;
for (int i = l; i <= r; i++) {
int coins = nums[l - 1] * nums[i] * nums[r + 1];
coins += dfs(nums, l, i - 1, dp) + dfs(nums, i + 1, r, dp);
dp[l][r] = max(dp[l][r], coins);
}
return dp[l][r];
}
};
JavaScript
class Solution {
/**
* @param {number[]} nums
* @return {number}
*/
maxCoins(nums) {
let n = nums.length;
let newNums = new Array(n + 2).fill(1);
for (let i = 0; i < n; i++) {
newNums[i + 1] = nums[i];
}
let dp = Array.from({ length: n + 2 }, () => new Array(n + 2).fill(-1));
return this.dfs(newNums, 1, newNums.length - 2, dp);
}
/**
* @param {number[]} nums
* @param {number} l
* @param {number} r
* @param {number[][]} dp
* @return {number}
*/
dfs(nums, l, r, dp) {
if (l > r) return 0;
if (dp[l][r] !== -1) return dp[l][r];
dp[l][r] = 0;
for (let i = l; i <= r; i++) {
let coins = nums[l - 1] * nums[i] * nums[r + 1];
coins +=
this.dfs(nums, l, i - 1, dp) + this.dfs(nums, i + 1, r, dp);
dp[l][r] = Math.max(dp[l][r], coins);
}
return dp[l][r];
}
}
C#
public class Solution {
public int MaxCoins(int[] nums) {
int n = nums.Length;
int[] newNums = new int[n + 2];
newNums[0] = newNums[n + 1] = 1;
for (int i = 0; i < n; i++) {
newNums[i + 1] = nums[i];
}
int[,] dp = new int[n + 2, n + 2];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
dp[i, j] = -1;
}
}
return Dfs(newNums, 1, newNums.Length - 2, dp);
}
public int Dfs(int[] nums, int l, int r, int[,] dp) {
if (l > r) return 0;
if (dp[l, r] != -1) return dp[l, r];
dp[l, r] = 0;
for (int i = l; i <= r; i++) {
int coins = nums[l - 1] * nums[i] * nums[r + 1];
coins += Dfs(nums, l, i - 1, dp) + Dfs(nums, i + 1, r, dp);
dp[l, r] = Math.Max(dp[l, r], coins);
}
return dp[l, r];
}
}
Go
func maxCoins(nums []int) int {
nums = append([]int{1}, nums...)
nums = append(nums, 1)
n := len(nums)
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, n)
}
var dfs func(l, r int) int
dfs = func(l, r int) int {
if l > r {
return 0
}
if dp[l][r] > 0 {
return dp[l][r]
}
dp[l][r] = 0
for i := l; i <= r; i++ {
coins := nums[l-1] * nums[i] * nums[r+1]
coins += dfs(l, i-1) + dfs(i+1, r)
dp[l][r] = max(dp[l][r], coins)
}
return dp[l][r]
}
return dfs(1, len(nums)-2)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
Kotlin
class Solution {
fun maxCoins(nums: IntArray): Int {
val newNums = intArrayOf(1) + nums + intArrayOf(1)
val n = newNums.size
val dp = Array(n) { IntArray(n) }
fun dfs(l: Int, r: Int): Int {
if (l > r) return 0
if (dp[l][r] > 0) return dp[l][r]
dp[l][r] = 0
for (i in l..r) {
val coins = newNums[l - 1] * newNums[i] * newNums[r + 1]
val totalCoins = coins + dfs(l, i - 1) + dfs(i + 1, r)
dp[l][r] = maxOf(dp[l][r], totalCoins)
}
return dp[l][r]
}
return dfs(1, newNums.size - 2)
}
}
Swift
class Solution {
func maxCoins(_ nums: [Int]) -> Int {
var nums = [1] + nums + [1]
let n = nums.count
var dp = Array(repeating: Array(repeating: -1, count: n), count: n)
func dfs(_ l: Int, _ r: Int) -> Int {
if l > r {
return 0
}
if dp[l][r] != -1 {
return dp[l][r]
}
dp[l][r] = 0
for i in l...r {
let coins = nums[l - 1] * nums[i] * nums[r + 1] + dfs(l, i - 1) + dfs(i + 1, r)
dp[l][r] = max(dp[l][r], coins)
}
return dp[l][r]
}
return dfs(1, n - 2)
}
}
Rust
impl Solution {
pub fn max_coins(nums: Vec<i32>) -> i32 {
let n = nums.len();
let mut new_nums = vec![1];
new_nums.extend_from_slice(&nums);
new_nums.push(1);
let mut dp = vec![vec![-1i32; n + 2]; n + 2];
fn dfs(nums: &[i32], l: i32, r: i32, dp: &mut Vec<Vec<i32>>) -> i32 {
if l > r {
return 0;
}
let (lu, ru) = (l as usize, r as usize);
if dp[lu][ru] != -1 {
return dp[lu][ru];
}
dp[lu][ru] = 0;
for i in l..=r {
let coins = nums[(l - 1) as usize] * nums[i as usize] * nums[(r + 1) as usize];
let total = coins + dfs(nums, l, i - 1, dp) + dfs(nums, i + 1, r, dp);
dp[lu][ru] = dp[lu][ru].max(total);
}
dp[lu][ru]
}
dfs(&new_nums, 1, new_nums.len() as i32 - 2, &mut dp)
}
}
4.4 复杂度分析
- 时间复杂度:——约 个状态,每个状态内枚举
i需要 ; - 空间复杂度:——备忘录
dp的规模。
4.5 仓库源码对照
仓库中的 cpp/0312-burst-balloons.cpp 正是这种"记忆化 + 补边"写法的工程化实现,其关键注释完整对应上文算法步骤:
memo用二维vector<vector<int>>缓存,初始化为0;- 递归入口为
dp(nums, memo, 1, n - 2),注释明确说明1与n - 2是不能戳破的假气球(补的边界1); - 基础情形
right - left < 0即空区间,返回0; - 枚举
i时收益为nums[left - 1] * nums[i] * nums[right + 1],再递归两侧。
而 java/0312-burst-balloons.java 给出了一种不补边的等价写法:它在计算 coins 时用 left - 1 >= 0 与 right + 1 < nums.length 显式判界,未越界才参与乘法,效果与补 1 完全一致。两种实现互相对照,有助于理解"补边只是化简边界,不是唯一方案"。
5. 解法三:自底向上动态规划(区间 DP 填表)
5.1 直觉(Intuition)
我们希望找到最优爆炸顺序下的最大金币数。核心技巧依然是反向思考:
在一个区间内,选择哪个气球是"最后被戳破"的。
如果只看 l 到 r 之间的气球,且气球 i 是该区间内最后一个被戳破的,那么:
(l..r)内除i外的气球都已消失;- 因此
i的邻居被固定为new_nums[l - 1]与new_nums[r + 1]; - 最后戳破
i的收益是:new_nums[l - 1] * new_nums[i] * new_nums[r + 1]。
最后戳破 i 后,剩余问题分裂为两个独立子问题:
- 区间
[l .. i-1]的最优收益; - 区间
[i+1 .. r]的最优收益。
这使得该问题成为标准区间 DP。
5.2 算法步骤
- 构造新数组
new_nums = [1] + nums + [1],方便处理边界; - 令
dp[l][r]表示戳破new_nums中下标l到r的气球所能获得的最大硬币数; - 将
dp初始化为0(空区间收益为0); - 按区间长度递增填充 DP 表:
l从n递减到1;r从l递增到n;
- 对每个区间
[l, r],枚举[l, r]内每个气球i作为最后一个被戳破的:- 最后戳破
i的收益:new_nums[l - 1] * new_nums[i] * new_nums[r + 1]; - 加上左子区间最优:
dp[l][i - 1]; - 加上右子区间最优:
dp[i + 1][r]; - 对所有
i取最大值;
- 最后戳破
- 最终答案存放在
dp[1][n],表示戳破所有原始气球的最大收益。
5.3 多语言实现
Python
class Solution:
def maxCoins(self, nums):
n = len(nums)
new_nums = [1] + nums + [1]
dp = [[0] * (n + 2) for _ in range(n + 2)]
for l in range(n, 0, -1):
for r in range(l, n + 1):
for i in range(l, r + 1):
coins = new_nums[l - 1] * new_nums[i] * new_nums[r + 1]
coins += dp[l][i - 1] + dp[i + 1][r]
dp[l][r] = max(dp[l][r], coins)
return dp[1][n]
Java
public class Solution {
public int maxCoins(int[] nums) {
int n = nums.length;
int[] newNums = new int[n + 2];
newNums[0] = newNums[n + 1] = 1;
for (int i = 0; i < n; i++) {
newNums[i + 1] = nums[i];
}
int[][] dp = new int[n + 2][n + 2];
for (int l = n; l >= 1; l--) {
for (int r = l; r <= n; r++) {
for (int i = l; i <= r; i++) {
int coins = newNums[l - 1] * newNums[i] * newNums[r + 1];
coins += dp[l][i - 1] + dp[i + 1][r];
dp[l][r] = Math.max(dp[l][r], coins);
}
}
}
return dp[1][n];
}
}
C++
class Solution {
public:
int maxCoins(vector<int>& nums) {
int n = nums.size();
vector<int> newNums(n + 2, 1);
for (int i = 0; i < n; i++) {
newNums[i + 1] = nums[i];
}
vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
for (int l = n; l >= 1; l--) {
for (int r = l; r <= n; r++) {
for (int i = l; i <= r; i++) {
int coins = newNums[l - 1] * newNums[i] * newNums[r + 1];
coins += dp[l][i - 1] + dp[i + 1][r];
dp[l][r] = max(dp[l][r], coins);
}
}
}
return dp[1][n];
}
};
JavaScript
class Solution {
/**
* @param {number[]} nums
* @return {number}
*/
maxCoins(nums) {
let n = nums.length;
let newNums = new Array(n + 2).fill(1);
for (let i = 0; i < n; i++) {
newNums[i + 1] = nums[i];
}
let dp = Array.from({ length: n + 2 }, () => new Array(n + 2).fill(0));
for (let l = n; l >= 1; l--) {
for (let r = l; r <= n; r++) {
for (let i = l; i <= r; i++) {
let coins = newNums[l - 1] * newNums[i] * newNums[r + 1];
coins += dp[l][i - 1] + dp[i + 1][r];
dp[l][r] = Math.max(dp[l][r], coins);
}
}
}
return dp[1][n];
}
}
C#
public class Solution {
public int MaxCoins(int[] nums) {
int n = nums.Length;
int[] newNums = new int[n + 2];
newNums[0] = newNums[n + 1] = 1;
for (int i = 0; i < n; i++) {
newNums[i + 1] = nums[i];
}
int[,] dp = new int[n + 2, n + 2];
for (int l = n; l >= 1; l--) {
for (int r = l; r <= n; r++) {
for (int i = l; i <= r; i++) {
int coins = newNums[l - 1] * newNums[i] * newNums[r + 1];
coins += dp[l, i - 1] + dp[i + 1, r];
dp[l, r] = Math.Max(dp[l, r], coins);
}
}
}
return dp[1, n];
}
}
Go
func maxCoins(nums []int) int {
n := len(nums)
newNums := append([]int{1}, nums...)
newNums = append(newNums, 1)
dp := make([][]int, n+2)
for i := range dp {
dp[i] = make([]int, n+2)
}
for l := n; l >= 1; l-- {
for r := l; r <= n; r++ {
for i := l; i <= r; i++ {
coins := newNums[l-1] * newNums[i] * newNums[r+1]
coins += dp[l][i-1] + dp[i+1][r]
dp[l][r] = max(dp[l][r], coins)
}
}
}
return dp[1][n]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
Kotlin
class Solution {
fun maxCoins(nums: IntArray): Int {
val n = nums.size
val newNums = intArrayOf(1) + nums + intArrayOf(1)
val dp = Array(n + 2) { IntArray(n + 2) }
for (l in n downTo 1) {
for (r in l..n) {
for (i in l..r) {
val coins = newNums[l - 1] * newNums[i] * newNums[r + 1]
dp[l][r] = maxOf(dp[l][r], coins + dp[l][i - 1] + dp[i + 1][r])
}
}
}
return dp[1][n]
}
}
Swift
class Solution {
func maxCoins(_ nums: [Int]) -> Int {
let n = nums.count
var newNums = [1] + nums + [1]
var dp = Array(repeating: Array(repeating: 0, count: n + 2), count: n + 2)
for l in stride(from: n, through: 1, by: -1) {
for r in l...n {
for i in l...r {
let coins = (newNums[l - 1] * newNums[i] * newNums[r + 1]) +
dp[l][i - 1] + dp[i + 1][r]
dp[l][r] = max(dp[l][r], coins)
}
}
}
return dp[1][n]
}
}
Rust
impl Solution {
pub fn max_coins(nums: Vec<i32>) -> i32 {
let n = nums.len();
let mut new_nums = vec![1];
new_nums.extend_from_slice(&nums);
new_nums.push(1);
let mut dp = vec![vec![0i32; n + 2]; n + 2];
for l in (1..=n).rev() {
for r in l..=n {
for i in l..=r {
let coins = new_nums[l - 1] * new_nums[i] * new_nums[r + 1];
let total = coins + dp[l][i - 1] + dp[i + 1][r];
dp[l][r] = dp[l][r].max(total);
}
}
}
dp[1][n]
}
}
5.4 复杂度分析
- 时间复杂度:;
- 空间复杂度:。
5.5 仓库源码对照:两种不同的填表视角
仓库中 python/0312-burst-balloons.py 给出了同等的自底向上写法,但采用"按 offset(区间长度)枚举"的视角,非常值得对照学习:
class Solution:
def maxCoins(self, nums: List[int]) -> int:
cache = {}
nums = [1] + nums + [1]
for offset in range(2, len(nums)):
for left in range(len(nums) - offset):
right = left + offset
for pivot in range(left + 1, right):
coins = nums[left] * nums[pivot] * nums[right]
coins += cache.get((left, pivot), 0) + cache.get((pivot, right), 0)
cache[(left, right)] = max(coins, cache.get((left, right), 0))
return cache.get((0, len(nums) - 1), 0)
两者唯一的区别在于区间枚举顺序:
- 前文解法三:
l从n递减、r从l递增,天然保证"小区间先于大区间"被计算; - 仓库 Python 版:直接按区间长度
offset从小到大枚举(left, right)对,同样保证依赖的子区间(left, pivot)与(pivot, right)都是更短的区间、必然已被缓存。
仓库的 javascript/0312-burst-balloons.js 更是在同一文件中同时给出了 Top-Down(memo)与 Bottom-Up(tabu)两套完整实现,且每个语句都标注了时间/空间贡献,例如:
- Top-Down 版中
search以left = 1, right = nums.length - 2为默认参数启动,memo初始化为-1表示"未计算"; - Bottom-Up 版中
initTabu生成(n+2) × (n+2)的全0表,tabu[1][nums.length]即最终答案,与上文dp[1][n]完全对应。
6. 常见误区(Common Pitfalls)
本节汇总了初学者最容易踩的五个坑,均来自原文档的完整清单。
6.1 只想着"第一个戳破谁",而不是"最后一个戳破谁"
关键洞察是:考虑区间内最后被戳破的气球,而非最先被戳破的。
- 若先戳破第一个,剩余数组结构会不可预期地改变,子问题之间相互纠缠、无法独立;
- 若最后一个戳破,则其边界邻居是固定的(
nums[l-1]与nums[r+1]),左右两侧可独立求解。
# 错误的心智模型:先戳破气球 i
# 剩余数组的结构会不可预测地变化
# 正确:在区间 [l, r] 中最后戳破气球 i
# i 的邻居固定为 nums[l-1] 与 nums[r+1]
6.2 忘记给数组两端补 1
题目规定越界的邻居按数值 1 处理。若忘记在数组两端各补一个 1,会在边界处出现索引错误或金币计算错误。
# 错误:使用原始数组
nums = [3, 1, 5, 8]
# 正确:两端补 1
nums = [1] + nums + [1] # [1, 3, 1, 5, 8, 1]
6.3 自底向上 DP 的循环顺序写错
自底向上填表时,小区间必须先于大区间被计算。左端点 l 应递减遍历,而 r 应递增遍历。顺序写反会读到尚未计算的 dp 值(读到的全是初始 0),导致答案错误。
# 正确顺序(前文解法三):
for l in range(n, 0, -1): # l 递减
for r in range(l, n + 1): # r 递增
...
6.4 金币计算用错邻居
当气球 i 是区间 [l, r] 内最后被戳破的时,它的邻居是区间边界 nums[l-1] 与 nums[r+1],而不是相邻下标 nums[i-1] 与 nums[i+1](这两者在 i 最后被戳破时早已被戳掉了)。
# 错误:使用相邻下标
coins = nums[i-1] * nums[i] * nums[i+1]
# 正确:使用区间边界
coins = nums[l-1] * nums[i] * nums[r+1]
6.5 遗漏空区间的基础情形
当 l > r 时区间内没有任何气球,收益应为 0。遗漏该基础情形会导致递归无法终止,或出现数组越界错误。Top-Down 版的 if (l > r) return 0 与 Bottom-Up 版将 dp 初始化为 0,都是在处理这一情形。
7. 复杂度总览与思路复盘
| 解法 | 时间 | 空间 | 关键思想 |
|---|---|---|---|
| 暴力递归 | 每次选择"第一个"戳破,不断复制数组 | ||
| Top-Down DP | 选择"最后一个"戳破 + 备忘录缓存 | ||
| Bottom-Up DP | 选择"最后一个"戳破 + 按区间长度填表 |
hints/burst-balloons.md 中给出的目标复杂度也印证了这一点:应追求 时间、 空间(其中 n 为输入数组大小)。其四步提示完整复现了本文章的推导路径:
- 先尝试递归模拟:遍历、弹出元素、递归两侧,但这是指数级的,需要观察子问题而非修改数组;
- 不传数组而传区间
(l, r),数组两端补1,思考"反向工程式"的弹出; - 把每个元素当作当前区间最后被弹出的:用
l-1与r+1处的元素相乘,再递归求解(l, i-1)与(i+1, r); - 用哈希表或二维数组做记忆化,缓存
(l, r)的结果。
8. 总结
Burst Balloons 之所以是"区间 DP 的标杆题",在于它要求你彻底反转直觉:先戳破谁并不重要,重要的是"最后戳破谁"——只有最后一个戳破的气球,其邻居才是确定且可推导的,子问题才能独立。从暴力递归()到记忆化( / ),再到循环填表,三种解法层层递进,配合本仓库 articles/burst-balloons.md、python/0312-burst-balloons.py、cpp/0312-burst-balloons.cpp、java/0312-burst-balloons.java、javascript/0312-burst-balloons.js 与 hints/burst-balloons.md 的对照阅读,你可以同时掌握"补边技巧"、"反向枚举"与"区间 DP 两种填表顺序"这三项可迁移到其他区间 DP 题目(如矩阵链乘、戳气球变体)的核心能力。