LeetCode 0312 Burst Balloons 完全题解:从暴力递归到区间 DP 的三种解法演进

原创2026-09-16 20:28:411,910 阅读
文章标签:示例工程教程

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. 在数组开头与结尾各加入一个 1,安全处理边界;
  2. 定义递归函数 dfs(nums):
    • nums 表示当前剩余气球列表;
  3. 若只剩两个边界 1(即没有真实气球):
    • 返回 0;
  4. 初始化 maxCoins = 0;
  5. 遍历两个边界之间的每个气球下标 i:
    • 计算戳破 nums[i] 所得硬币:nums[i - 1] * nums[i] * nums[i + 1];
    • 递归计算剩余气球的最大收益:删除 nums[i] 后对新列表调用 dfs;
    • 用最优结果更新 maxCoins;
  6. 返回当前配置的 maxCoins;
  7. 用完整的补边数组启动递归并返回结果。

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 复杂度分析

  • 时间复杂度:O(n⋅2n)O(n \cdot 2^n)——每次递归都要遍历并复制数组,指数爆炸;
  • 空间复杂度:O(n⋅2n)O(n \cdot 2^n)——递归调用栈与数组拷贝的开销。

这种解法在 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. 数组两端各加 1,免去边界判断;
  2. 使用备忘录 dp,其中 dp[(l, r)] 存储区间 [l, r] 内气球可得到的最大硬币数;
  3. 定义递归函数 dfs(l, r):
    • 若 l > r,返回 0(无气球可戳);
    • 若 (l, r) 已计算过,直接返回缓存值;
  4. 枚举区间 [l, r] 内的每个气球 i 作为最后一个被戳破的:
    • 最后戳破 i 的收益:nums[l - 1] * nums[i] * nums[r + 1];
    • 加上左侧最优:dfs(l, i - 1);
    • 加上右侧最优:dfs(i + 1, r);
    • 对所有 i 取最大值;
  5. 将最优值存入 dp[(l, r)] 并返回;
  6. 最终答案为 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 复杂度分析

  • 时间复杂度:O(n3)O(n^3)——约 O(n2)O(n^2) 个状态,每个状态内枚举 i 需要 O(n)O(n);
  • 空间复杂度:O(n2)O(n^2)——备忘录 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 算法步骤

  1. 构造新数组 new_nums = [1] + nums + [1],方便处理边界;
  2. 令 dp[l][r] 表示戳破 new_nums 中下标 l 到 r 的气球所能获得的最大硬币数;
  3. 将 dp 初始化为 0(空区间收益为 0);
  4. 按区间长度递增填充 DP 表:
    • l 从 n 递减到 1;
    • r 从 l 递增到 n;
  5. 对每个区间 [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 取最大值;
  6. 最终答案存放在 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 复杂度分析

  • 时间复杂度:O(n3)O(n^3);
  • 空间复杂度:O(n2)O(n^2)。

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. 复杂度总览与思路复盘

解法 时间 空间 关键思想
暴力递归 O(n⋅2n)O(n \cdot 2^n) O(n⋅2n)O(n \cdot 2^n) 每次选择"第一个"戳破,不断复制数组
Top-Down DP O(n3)O(n^3) O(n2)O(n^2) 选择"最后一个"戳破 + 备忘录缓存
Bottom-Up DP O(n3)O(n^3) O(n2)O(n^2) 选择"最后一个"戳破 + 按区间长度填表

hints/burst-balloons.md 中给出的目标复杂度也印证了这一点:应追求 O(n3)O(n^3) 时间、O(n2)O(n^2) 空间(其中 n 为输入数组大小)。其四步提示完整复现了本文章的推导路径:

  1. 先尝试递归模拟:遍历、弹出元素、递归两侧,但这是指数级的,需要观察子问题而非修改数组;
  2. 不传数组而传区间 (l, r),数组两端补 1,思考"反向工程式"的弹出;
  3. 把每个元素当作当前区间最后被弹出的:用 l-1 与 r+1 处的元素相乘,再递归求解 (l, i-1) 与 (i+1, r);
  4. 用哈希表或二维数组做记忆化,缓存 (l, r) 的结果。

8. 总结

Burst Balloons 之所以是"区间 DP 的标杆题",在于它要求你彻底反转直觉:先戳破谁并不重要,重要的是"最后戳破谁"——只有最后一个戳破的气球,其邻居才是确定且可推导的,子问题才能独立。从暴力递归(O(n⋅2n)O(n \cdot 2^n))到记忆化(O(n3)O(n^3) / O(n2)O(n^2)),再到循环填表,三种解法层层递进,配合本仓库 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 题目(如矩阵链乘、戳气球变体)的核心能力。

登录后查看全文
leetcode