 优化实战)
LeetCode 312 戳气球Burst Balloons全解从暴力递归到区间 DP 的 O(n³) 优化实战【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文基于本仓库 hints/burst-balloons.md 的阶梯式提示与 articles/burst-balloons.md 的完整解法文章系统讲解 LeetCode 312「戳气球」这道经典区间动态规划题。文章从指数级暴力递归出发推导出「最后一个被戳破的气球」这一核心逆向思维并给出自顶向下记忆化与自底向上表格化两种 O(n³) 解法配套 Python、Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust 多语言实现与仓库源码佐证。读完你将掌握区间 DP 的建模套路、边界填充技巧与复杂度分析方法并能在面试中独立写出可运行的满分答案。题目回顾为什么这道题是区间 DP 的典范LeetCode 312「戳气球」要求你给定n个气球编号0到n - 1每个气球上有一个数字nums[i]。戳破第i个气球获得的硬币数为nums[i - 1] * nums[i] * nums[i 1]其中越界位置视为数值1的虚拟气球。戳破一个气球后左右两侧气球会成为新的邻居你可以按任意顺序戳破所有气球求能获得的最大硬币总数。这道题之所以经典是因为它的收益函数依赖动态变化的邻居戳破一个气球会改变其他气球的邻接关系因此「当前该戳哪个」并没有贪心可循只能枚举所有顺序。而枚举顺序的空间是n!必须靠 DP 压缩状态。仓库中的 python/0312-burst-balloons.py 等 10 余种语言实现c、cpp、csharp、java、javascript、kotlin、python、swift、typescript 目录下的0312-burst-balloons.*全部围绕区间 DP 建模是学习该题型的标准素材。前置知识在动手写代码前建议确认你已具备以下基础与 articles/burst-balloons.md 的 Prerequisites 一致递归能把大问题分解为结构相同的子问题动态规划掌握记忆化memoization与表格化tabulation两种优化手段区间 DP能按「考虑所有子区间并合并结果」的方式建模数组边界处理通过填充哨兵值简化边界判断。思路一暴力递归 —— 以指数复杂度理解问题结构直觉最直接的思路是模拟真实过程每次从剩余气球中挑一个戳破获得左邻居 × 当前气球 × 右邻居的硬币然后递归处理剩下的气球。递归函数语义为「当前剩余气球列表能获得的最大硬币数」。为了让每个气球在任何时刻都有左右邻居我们在数组两端各补一个1视为永不戳破的虚拟气球。当剩余列表只剩两个1时没有真实气球可戳返回0。hints 的 Hint 1 正是引导你先写出这种模拟式递归Try to simulate the process recursively by passing the array to the recursive function. At each step, iterate through the array, pop an element, and recursively apply the same process to the two subarrays on both sides of the popped element, returning the maximum result from all recursive paths.注意这里的措辞是「pop an element, and recursively apply the same process to the two subarrays onboth sides」但实际上戳破中间一个气球后两侧气球会合并成一个连续列表邻居关系被打乱这正是该暴力方法低效且难以记忆化的根本原因。算法步骤在数组首尾各插入1定义dfs(nums)nums为当前剩余气球列表若只剩两个边界1返回0遍历i 1到len(nums) - 2对每个候选气球本次收益 nums[i-1] * nums[i] * nums[i1]递归收益 dfs(移除 nums[i] 后的新列表)更新全局最大值返回当前列表的最大硬币数。多语言实现暴力版Python与 articles/burst-balloons.md 一致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)C 版本class Solution { public: int maxCoins(vectorint nums) { nums.insert(nums.begin(), 1); nums.push_back(1); return dfs(nums); } int dfs(vectorint 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]; vectorint newNums nums; newNums.erase(newNums.begin() i); coins dfs(newNums); maxCoins max(maxCoins, coins); } return maxCoins; } };复杂度分析每次递归都要复制并删除一个元素产生O(n)的数组构造开销而状态数是O(n!)量级所有戳破顺序因此时间复杂度O(n × 2^n)每层分支数随剩余气球数递减总体呈指数增长articles 中记为O(n*2^n)空间复杂度O(n × 2^n)递归深度O(n)加上每层构造的新数组副本。n 20时该算法已基本不可行必须优化。思路二关键逆向思维 —— 选「最后一个被戳破」的气球暴力版低效的根源在于戳破顺序不同邻居关系随之改变子问题之间互相纠缠无法直接记忆化。hints 的 Hint 2 给出了突破口Instead of passing the array, we can pass the range of indiceslandrthat need to be processed. We pad the input array with1s on both sides for easier computation, butlandrrepresent the first and last indices of the original input array. Can you think of a reverse engineering approach for popping elements?即不再传整个数组而是传区间[l, r]并思考「逆向工程」——假设我们关心的不是第一个被戳破的而是最后一个被戳破的气球。为什么选「最后一个」是神来之笔假设在区间[l, r]内气球i是最后一个被戳破的那么此时(l, r)内除i外的所有气球都已被戳破因此i的左右邻居是固定的左边是nums[l-1]右边是nums[r1]它们要么是区间外的真实气球要么是补上的1本次收益 nums[l-1] * nums[i] * nums[r1]剩余问题被干净地拆分为两个相互独立的子区间[l, i-1]与[i1, r]。这与「第一个被戳破」形成鲜明对比若选第一个剩余数组结构会因两侧合并而不可预测无法拆分为独立子问题。状态定义定义dp[l][r]或记忆化键(l, r)表示在补了1的数组中戳破区间[l, r]内所有气球能获得的最大硬币数。转移方程dp[l][r] max over i in [l, r] of ( nums[l-1] * nums[i] * nums[r1] dp[l][i-1] dp[i1][r] )边界条件l r时区间为空收益为0。最终答案dp[1][n]n为原始气球数下标从 1 开始因为两端各补了一个1。hints 的 Hint 3 精确描述了这一步We determine the result by considering each element as the last one to be popped in the current range. For each element, we calculate its value by multiplying it with the elements atl - 1andr 1, then recursively solve the subproblems for the ranges(l, i - 1)and(i 1, r).思路三自顶向下记忆化 DPTop-Down直觉暴力递归中存在大量重复子问题——同一个区间[l, r]会在不同戳破顺序下被反复求解。hints 的 Hint 4 建议We can use memoization to cache the results of recursive calls and avoid redundant calculations. A hash map or a2Darray can be used to store results since the recursive function parameterslandrare within the range of the input array size.由于l、r的取值范围不超过数组大小用二维数组即可完成缓存。算法步骤数组两端补1建立记忆化表dp哈希表或二维数组定义dfs(l, r)若l r返回0若(l, r)已计算直接返回缓存值枚举i ∈ [l, r]作为最后一个被戳破的气球收益 nums[l-1] * nums[i] * nums[r1] dfs(l, i-1) dfs(i1, r)取最大值缓存并返回dp[l][r]答案 dfs(1, len(nums) - 2)。多语言实现Top-DownPython哈希表版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二维数组版仓库 java/0312-burst-balloons.java 采用类似思路注释明确标注Time Complexity: O(n^3)、Extra Space Complexity: O(n^2)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仓库 cpp/0312-burst-balloons.cpp 的实现注释完整解释了「think backwards」的核心思想class Solution { public: int maxCoins(vectorint nums) { // add 1 before after nums nums.insert(nums.begin(), 1); nums.insert(nums.end(), 1); int n nums.size(); // cache results of dp vectorvectorint memo(n, vectorint(n, 0)); // 1 n - 2 since we cant burst our fake balloons return dp(nums, memo, 1, n - 2); } private: int dp(vectorint nums, vectorvectorint memo, int left, int right) { // base case interval is empty, yields 0 coins if (right - left 0) { return 0; } // weve already seen this, return from cache if (memo[left][right] 0) { return memo[left][right]; } // find the last burst in nums[left]...nums[right] int result 0; for (int i left; i right; i) { // nums[i] is the last burst int curr nums[left - 1] * nums[i] * nums[right 1]; int remaining dp(nums, memo, left, i - 1) dp(nums, memo, i 1, right); result max(result, curr remaining); } memo[left][right] result; return result; } };C#、Go、Kotlin、Swift、Rust 的完整实现同样收录在 articles/burst-balloons.md 的多语言代码块中可直接对照阅读。复杂度分析共有O(n²)个区间状态每个状态枚举O(n)个候选i因此时间复杂度O(n³)空间复杂度O(n²)记忆化表。这也正是 hints 开头给出的目标复杂度O(n³)时间、O(n²)空间n为输入数组大小。思路四自底向上表格化 DPBottom-Up直觉Top-Down 与 Bottom-Up 的转移方程完全相同区别在于 Bottom-Up 显式地按区间长度从小到大填充dp表保证计算dp[l][r]时所有更短的子区间dp[l][i-1]、dp[i1][r]都已被算出从而无需递归与缓存判断。算法步骤构造new_nums [1] nums [1]定义dp[l][r]戳破new_nums[l..r]内所有气球的最大硬币数初始化为0空区间收益为 0按区间长度递增填充l从n递减到1r从l递增到n对每个区间[l, r]枚举i ∈ [l, r]作为最后一个被戳破的气球coins new_nums[l-1] * new_nums[i] * new_nums[r1] dp[l][i-1] dp[i1][r]取最大值写入dp[l][r]答案 dp[1][n]。多语言实现Bottom-UpPython与 articles/burst-balloons.md 一致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]JavaScriptTypeScript 版本见仓库 typescript/0312-burst-balloons.ts其按len从小到大递推逻辑等价class Solution { 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仓库 c/0312-burst-balloons.c 的实现使用memset清零二维 DP 数组len从 2 递增等价于按区间长度递推int max(int a, int b) { return (a b) ? a : b; } int maxCoins(int* nums, int numsSize) { // Add padding of 1 to both ends of the array int n numsSize 2; int paddedNums[n]; paddedNums[0] paddedNums[n - 1] 1; for (int i 1; i n - 1; i) { paddedNums[i] nums[i - 1]; } // Create a 2D DP array to store the results int dp[n][n]; memset(dp, 0, sizeof(dp)); // Start dynamic programming process for (int len 2; len n; len) { for (int left 0; left n - len; left) { int right left len; for (int k left 1; k right; k) { dp[left][right] max(dp[left][right], paddedNums[left] * paddedNums[k] * paddedNums[right] dp[left][k] dp[k][right]); } } } return dp[0][n - 1]; }注意 C 与 TypeScript 版采用 0 基区间dp[0][n-1]Python/Java/C/Go 等版本采用 1 基区间dp[1][n]二者只是下标约定不同转移本质完全一致。复杂度分析时间复杂度O(n³)O(n²)个状态 × 每个状态O(n)次枚举空间复杂度O(n²)二维 DP 表。三种复杂度对照来源hints/burst-balloons.md 与 articles/burst-balloons.md解法时间复杂度空间复杂度适用性暴力递归O(n × 2^n)O(n × 2^n)仅理解用n ≤ 10勉强可跑Top-Down 记忆化O(n³)O(n²)思路直观推荐面试演示Bottom-Up 表格化O(n³)O(n²)常数更小笔试/竞赛首选仓库源码中的另一种 Bottom-Up 形态缓存键为开区间值得注意仓库 python/0312-burst-balloons.py 采用了另一种等价写法——以开区间(left, right)为缓存键left、right本身是虚拟边界pivot是区间内最后一个被戳破的气球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)这里的dp(left, right)表示「戳破开区间(left, right)内的气球」pivot是该区间最后一个被戳破的气球其收益为nums[left] * nums[pivot] * nums[right]剩余两侧子问题为(left, pivot)与(pivot, right)。这与闭区间写法dp[l][r]l、r为真实气球下标在数学上完全等价只是把虚拟边界也纳入了缓存键。阅读源码时可以体会这两种索引约定的差异理解区间 DP 的两种常见建模方式。常见陷阱与避坑清单articles 的 Common Pitfalls 部分总结了五个高频错误这里逐条展开1. 想「第一个被戳破」而不是「最后一个」这是整道题最关键的一步。若思考第一个被戳破的气球剩余数组的邻居结构会随机变化子问题不独立而思考最后一个被戳破的气球时其边界邻居被固定为nums[l-1]与nums[r1]左右子区间完全独立。# 错误心智模型先戳破 i # 剩余数组结构不可预测无法拆分独立子问题 # 正确心智模型区间 [l, r] 中最后戳破 i # i 的邻居固定为 nums[l-1] 和 nums[r1]2. 忘记在数组两端补 1题目明确「越界邻居视为 1」。不补1会导致边界索引越界或边界气球收益计算错误。# 错误直接用原始数组 nums [3, 1, 5, 8] # 正确两端补 1 nums [1] nums [1] # [1, 3, 1, 5, 8, 1]3. 自底向上的循环顺序错误Bottom-Up 必须保证小区间先于大区间被计算l从大到小递减、r从小到大递增或显式按区间长度递增。若顺序写反会读取尚未计算完成的 DP 值。4. 收益计算用了错误的邻居当i是区间[l, r]中最后一个被戳破的气球时其邻居是区间边界外的nums[l-1]与nums[r1]而不是相邻下标nums[i-1]、nums[i1]。# 错误使用相邻下标 coins nums[i-1] * nums[i] * nums[i1] # 正确使用区间边界 coins nums[l-1] * nums[i] * nums[r1]5. 漏掉空区间基准情形当l r时区间内没有气球应返回0。遗漏该基准会导致递归无限深入或数组越界。举一反三区间 DP 的通用建模模板戳气球是区间 DP 的典型代表它的建模套路可以迁移到其他问题识别「合并/消除 收益依赖边界」的结构如矩阵链乘法、戳气球、布尔表达式求值、回文划分等逆向思维把「先做某操作」反转为「最后一个做某操作」使边界固定、子问题独立状态设计dp[l][r]表示闭区间或开区间内的最优值转移枚举区间内的分割点k合并dp[l][k-1]与dp[k1][r]或开区间写法dp[l][k] dp[k][r]填充顺序按区间长度从小到大或l递减、r递增。仓库中同类区间 DP 题还可参考 articles/burst-balloons.md 之外的 articles/minimum-number-of-arrows-to-burst-balloons.md贪心思路与本题形成对照以及cpp、java目录下的0312-burst-balloons.*多语言实现加深对同一题不同写法的理解。总结LeetCode 312 的核心收获可以浓缩为三点暴力递归模拟戳破顺序指数级不可行但帮助我们确认问题结构逆向思维最后一个被戳破让收益只依赖固定的区间边界nums[l-1]、nums[r1]从而把问题拆成两个独立子区间区间 DPTop-Down 记忆化或 Bottom-Up 表格化把复杂度从O(n × 2^n)降到O(n³)时间、O(n²)空间满足 hints 给出的目标复杂度要求。配套的完整多语言代码Python / Java / C / JavaScript / C# / Go / Kotlin / Swift / Rust与逐步提示可在 articles/burst-balloons.md 和 hints/burst-balloons.md 中查看仓库各语言目录下的0312-burst-balloons.*文件则是可直接运行验证的参考实现。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 312 戳气球（Burst Balloons）全解：从暴力递归到区间 DP 的 O(n³) 优化实战
LeetCode 312 戳气球Burst Balloons全解从暴力递归到区间 DP 的 O(n³) 优化实战【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文基于本仓库 hints/burst-balloons.md 的阶梯式提示与 articles/burst-balloons.md 的完整解法文章系统讲解 LeetCode 312「戳气球」这道经典区间动态规划题。文章从指数级暴力递归出发推导出「最后一个被戳破的气球」这一核心逆向思维并给出自顶向下记忆化与自底向上表格化两种 O(n³) 解法配套 Python、Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust 多语言实现与仓库源码佐证。读完你将掌握区间 DP 的建模套路、边界填充技巧与复杂度分析方法并能在面试中独立写出可运行的满分答案。题目回顾为什么这道题是区间 DP 的典范LeetCode 312「戳气球」要求你给定n个气球编号0到n - 1每个气球上有一个数字nums[i]。戳破第i个气球获得的硬币数为nums[i - 1] * nums[i] * nums[i 1]其中越界位置视为数值1的虚拟气球。戳破一个气球后左右两侧气球会成为新的邻居你可以按任意顺序戳破所有气球求能获得的最大硬币总数。这道题之所以经典是因为它的收益函数依赖动态变化的邻居戳破一个气球会改变其他气球的邻接关系因此「当前该戳哪个」并没有贪心可循只能枚举所有顺序。而枚举顺序的空间是n!必须靠 DP 压缩状态。仓库中的 python/0312-burst-balloons.py 等 10 余种语言实现c、cpp、csharp、java、javascript、kotlin、python、swift、typescript 目录下的0312-burst-balloons.*全部围绕区间 DP 建模是学习该题型的标准素材。前置知识在动手写代码前建议确认你已具备以下基础与 articles/burst-balloons.md 的 Prerequisites 一致递归能把大问题分解为结构相同的子问题动态规划掌握记忆化memoization与表格化tabulation两种优化手段区间 DP能按「考虑所有子区间并合并结果」的方式建模数组边界处理通过填充哨兵值简化边界判断。思路一暴力递归 —— 以指数复杂度理解问题结构直觉最直接的思路是模拟真实过程每次从剩余气球中挑一个戳破获得左邻居 × 当前气球 × 右邻居的硬币然后递归处理剩下的气球。递归函数语义为「当前剩余气球列表能获得的最大硬币数」。为了让每个气球在任何时刻都有左右邻居我们在数组两端各补一个1视为永不戳破的虚拟气球。当剩余列表只剩两个1时没有真实气球可戳返回0。hints 的 Hint 1 正是引导你先写出这种模拟式递归Try to simulate the process recursively by passing the array to the recursive function. At each step, iterate through the array, pop an element, and recursively apply the same process to the two subarrays on both sides of the popped element, returning the maximum result from all recursive paths.注意这里的措辞是「pop an element, and recursively apply the same process to the two subarrays onboth sides」但实际上戳破中间一个气球后两侧气球会合并成一个连续列表邻居关系被打乱这正是该暴力方法低效且难以记忆化的根本原因。算法步骤在数组首尾各插入1定义dfs(nums)nums为当前剩余气球列表若只剩两个边界1返回0遍历i 1到len(nums) - 2对每个候选气球本次收益 nums[i-1] * nums[i] * nums[i1]递归收益 dfs(移除 nums[i] 后的新列表)更新全局最大值返回当前列表的最大硬币数。多语言实现暴力版Python与 articles/burst-balloons.md 一致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)C 版本class Solution { public: int maxCoins(vectorint nums) { nums.insert(nums.begin(), 1); nums.push_back(1); return dfs(nums); } int dfs(vectorint 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]; vectorint newNums nums; newNums.erase(newNums.begin() i); coins dfs(newNums); maxCoins max(maxCoins, coins); } return maxCoins; } };复杂度分析每次递归都要复制并删除一个元素产生O(n)的数组构造开销而状态数是O(n!)量级所有戳破顺序因此时间复杂度O(n × 2^n)每层分支数随剩余气球数递减总体呈指数增长articles 中记为O(n*2^n)空间复杂度O(n × 2^n)递归深度O(n)加上每层构造的新数组副本。n 20时该算法已基本不可行必须优化。思路二关键逆向思维 —— 选「最后一个被戳破」的气球暴力版低效的根源在于戳破顺序不同邻居关系随之改变子问题之间互相纠缠无法直接记忆化。hints 的 Hint 2 给出了突破口Instead of passing the array, we can pass the range of indiceslandrthat need to be processed. We pad the input array with1s on both sides for easier computation, butlandrrepresent the first and last indices of the original input array. Can you think of a reverse engineering approach for popping elements?即不再传整个数组而是传区间[l, r]并思考「逆向工程」——假设我们关心的不是第一个被戳破的而是最后一个被戳破的气球。为什么选「最后一个」是神来之笔假设在区间[l, r]内气球i是最后一个被戳破的那么此时(l, r)内除i外的所有气球都已被戳破因此i的左右邻居是固定的左边是nums[l-1]右边是nums[r1]它们要么是区间外的真实气球要么是补上的1本次收益 nums[l-1] * nums[i] * nums[r1]剩余问题被干净地拆分为两个相互独立的子区间[l, i-1]与[i1, r]。这与「第一个被戳破」形成鲜明对比若选第一个剩余数组结构会因两侧合并而不可预测无法拆分为独立子问题。状态定义定义dp[l][r]或记忆化键(l, r)表示在补了1的数组中戳破区间[l, r]内所有气球能获得的最大硬币数。转移方程dp[l][r] max over i in [l, r] of ( nums[l-1] * nums[i] * nums[r1] dp[l][i-1] dp[i1][r] )边界条件l r时区间为空收益为0。最终答案dp[1][n]n为原始气球数下标从 1 开始因为两端各补了一个1。hints 的 Hint 3 精确描述了这一步We determine the result by considering each element as the last one to be popped in the current range. For each element, we calculate its value by multiplying it with the elements atl - 1andr 1, then recursively solve the subproblems for the ranges(l, i - 1)and(i 1, r).思路三自顶向下记忆化 DPTop-Down直觉暴力递归中存在大量重复子问题——同一个区间[l, r]会在不同戳破顺序下被反复求解。hints 的 Hint 4 建议We can use memoization to cache the results of recursive calls and avoid redundant calculations. A hash map or a2Darray can be used to store results since the recursive function parameterslandrare within the range of the input array size.由于l、r的取值范围不超过数组大小用二维数组即可完成缓存。算法步骤数组两端补1建立记忆化表dp哈希表或二维数组定义dfs(l, r)若l r返回0若(l, r)已计算直接返回缓存值枚举i ∈ [l, r]作为最后一个被戳破的气球收益 nums[l-1] * nums[i] * nums[r1] dfs(l, i-1) dfs(i1, r)取最大值缓存并返回dp[l][r]答案 dfs(1, len(nums) - 2)。多语言实现Top-DownPython哈希表版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二维数组版仓库 java/0312-burst-balloons.java 采用类似思路注释明确标注Time Complexity: O(n^3)、Extra Space Complexity: O(n^2)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仓库 cpp/0312-burst-balloons.cpp 的实现注释完整解释了「think backwards」的核心思想class Solution { public: int maxCoins(vectorint nums) { // add 1 before after nums nums.insert(nums.begin(), 1); nums.insert(nums.end(), 1); int n nums.size(); // cache results of dp vectorvectorint memo(n, vectorint(n, 0)); // 1 n - 2 since we cant burst our fake balloons return dp(nums, memo, 1, n - 2); } private: int dp(vectorint nums, vectorvectorint memo, int left, int right) { // base case interval is empty, yields 0 coins if (right - left 0) { return 0; } // weve already seen this, return from cache if (memo[left][right] 0) { return memo[left][right]; } // find the last burst in nums[left]...nums[right] int result 0; for (int i left; i right; i) { // nums[i] is the last burst int curr nums[left - 1] * nums[i] * nums[right 1]; int remaining dp(nums, memo, left, i - 1) dp(nums, memo, i 1, right); result max(result, curr remaining); } memo[left][right] result; return result; } };C#、Go、Kotlin、Swift、Rust 的完整实现同样收录在 articles/burst-balloons.md 的多语言代码块中可直接对照阅读。复杂度分析共有O(n²)个区间状态每个状态枚举O(n)个候选i因此时间复杂度O(n³)空间复杂度O(n²)记忆化表。这也正是 hints 开头给出的目标复杂度O(n³)时间、O(n²)空间n为输入数组大小。思路四自底向上表格化 DPBottom-Up直觉Top-Down 与 Bottom-Up 的转移方程完全相同区别在于 Bottom-Up 显式地按区间长度从小到大填充dp表保证计算dp[l][r]时所有更短的子区间dp[l][i-1]、dp[i1][r]都已被算出从而无需递归与缓存判断。算法步骤构造new_nums [1] nums [1]定义dp[l][r]戳破new_nums[l..r]内所有气球的最大硬币数初始化为0空区间收益为 0按区间长度递增填充l从n递减到1r从l递增到n对每个区间[l, r]枚举i ∈ [l, r]作为最后一个被戳破的气球coins new_nums[l-1] * new_nums[i] * new_nums[r1] dp[l][i-1] dp[i1][r]取最大值写入dp[l][r]答案 dp[1][n]。多语言实现Bottom-UpPython与 articles/burst-balloons.md 一致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]JavaScriptTypeScript 版本见仓库 typescript/0312-burst-balloons.ts其按len从小到大递推逻辑等价class Solution { 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仓库 c/0312-burst-balloons.c 的实现使用memset清零二维 DP 数组len从 2 递增等价于按区间长度递推int max(int a, int b) { return (a b) ? a : b; } int maxCoins(int* nums, int numsSize) { // Add padding of 1 to both ends of the array int n numsSize 2; int paddedNums[n]; paddedNums[0] paddedNums[n - 1] 1; for (int i 1; i n - 1; i) { paddedNums[i] nums[i - 1]; } // Create a 2D DP array to store the results int dp[n][n]; memset(dp, 0, sizeof(dp)); // Start dynamic programming process for (int len 2; len n; len) { for (int left 0; left n - len; left) { int right left len; for (int k left 1; k right; k) { dp[left][right] max(dp[left][right], paddedNums[left] * paddedNums[k] * paddedNums[right] dp[left][k] dp[k][right]); } } } return dp[0][n - 1]; }注意 C 与 TypeScript 版采用 0 基区间dp[0][n-1]Python/Java/C/Go 等版本采用 1 基区间dp[1][n]二者只是下标约定不同转移本质完全一致。复杂度分析时间复杂度O(n³)O(n²)个状态 × 每个状态O(n)次枚举空间复杂度O(n²)二维 DP 表。三种复杂度对照来源hints/burst-balloons.md 与 articles/burst-balloons.md解法时间复杂度空间复杂度适用性暴力递归O(n × 2^n)O(n × 2^n)仅理解用n ≤ 10勉强可跑Top-Down 记忆化O(n³)O(n²)思路直观推荐面试演示Bottom-Up 表格化O(n³)O(n²)常数更小笔试/竞赛首选仓库源码中的另一种 Bottom-Up 形态缓存键为开区间值得注意仓库 python/0312-burst-balloons.py 采用了另一种等价写法——以开区间(left, right)为缓存键left、right本身是虚拟边界pivot是区间内最后一个被戳破的气球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)这里的dp(left, right)表示「戳破开区间(left, right)内的气球」pivot是该区间最后一个被戳破的气球其收益为nums[left] * nums[pivot] * nums[right]剩余两侧子问题为(left, pivot)与(pivot, right)。这与闭区间写法dp[l][r]l、r为真实气球下标在数学上完全等价只是把虚拟边界也纳入了缓存键。阅读源码时可以体会这两种索引约定的差异理解区间 DP 的两种常见建模方式。常见陷阱与避坑清单articles 的 Common Pitfalls 部分总结了五个高频错误这里逐条展开1. 想「第一个被戳破」而不是「最后一个」这是整道题最关键的一步。若思考第一个被戳破的气球剩余数组的邻居结构会随机变化子问题不独立而思考最后一个被戳破的气球时其边界邻居被固定为nums[l-1]与nums[r1]左右子区间完全独立。# 错误心智模型先戳破 i # 剩余数组结构不可预测无法拆分独立子问题 # 正确心智模型区间 [l, r] 中最后戳破 i # i 的邻居固定为 nums[l-1] 和 nums[r1]2. 忘记在数组两端补 1题目明确「越界邻居视为 1」。不补1会导致边界索引越界或边界气球收益计算错误。# 错误直接用原始数组 nums [3, 1, 5, 8] # 正确两端补 1 nums [1] nums [1] # [1, 3, 1, 5, 8, 1]3. 自底向上的循环顺序错误Bottom-Up 必须保证小区间先于大区间被计算l从大到小递减、r从小到大递增或显式按区间长度递增。若顺序写反会读取尚未计算完成的 DP 值。4. 收益计算用了错误的邻居当i是区间[l, r]中最后一个被戳破的气球时其邻居是区间边界外的nums[l-1]与nums[r1]而不是相邻下标nums[i-1]、nums[i1]。# 错误使用相邻下标 coins nums[i-1] * nums[i] * nums[i1] # 正确使用区间边界 coins nums[l-1] * nums[i] * nums[r1]5. 漏掉空区间基准情形当l r时区间内没有气球应返回0。遗漏该基准会导致递归无限深入或数组越界。举一反三区间 DP 的通用建模模板戳气球是区间 DP 的典型代表它的建模套路可以迁移到其他问题识别「合并/消除 收益依赖边界」的结构如矩阵链乘法、戳气球、布尔表达式求值、回文划分等逆向思维把「先做某操作」反转为「最后一个做某操作」使边界固定、子问题独立状态设计dp[l][r]表示闭区间或开区间内的最优值转移枚举区间内的分割点k合并dp[l][k-1]与dp[k1][r]或开区间写法dp[l][k] dp[k][r]填充顺序按区间长度从小到大或l递减、r递增。仓库中同类区间 DP 题还可参考 articles/burst-balloons.md 之外的 articles/minimum-number-of-arrows-to-burst-balloons.md贪心思路与本题形成对照以及cpp、java目录下的0312-burst-balloons.*多语言实现加深对同一题不同写法的理解。总结LeetCode 312 的核心收获可以浓缩为三点暴力递归模拟戳破顺序指数级不可行但帮助我们确认问题结构逆向思维最后一个被戳破让收益只依赖固定的区间边界nums[l-1]、nums[r1]从而把问题拆成两个独立子区间区间 DPTop-Down 记忆化或 Bottom-Up 表格化把复杂度从O(n × 2^n)降到O(n³)时间、O(n²)空间满足 hints 给出的目标复杂度要求。配套的完整多语言代码Python / Java / C / JavaScript / C# / Go / Kotlin / Swift / Rust与逐步提示可在 articles/burst-balloons.md 和 hints/burst-balloons.md 中查看仓库各语言目录下的0312-burst-balloons.*文件则是可直接运行验证的参考实现。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考