题目描述：
有
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] --> [] coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167示例 2：
输入：nums = [1,5]输出：10
解题思路：
方法一：动态规划
核心思路：区间 DP
正向思考很难：戳破一个气球后，左右邻居会变化，后续计算依赖当前状态。
反向思考：考虑最后一个被戳破的气球。假设最后戳破的是k，那么：
k左边的气球和右边的气球已经全部戳破k的邻居是虚拟的1（数组边界）最后戳破
k的收益 =1 × nums[k] × 1 = nums[k]
但更关键的是：最后戳破k之前，k把问题分成了左右两个独立的子问题。
状态定义：
在nums两边各加一个1，得到新数组val，长度为n + 2。
dp[i][j]= 戳破开区间(i, j)内所有气球能获得的最大硬币数。
注意：i和j是开区间，i和j位置的气球不戳破。
状态转移：
枚举(i, j)内最后一个被戳破的气球k：
dp[i][j] = max(dp[i][k] + dp[k][j] + val[i] * val[k] * val[j])
dp[i][k]：戳破(i, k)内的气球dp[k][j]：戳破(k, j)内的气球val[i] * val[k] * val[j]：最后戳破k的收益
具体过程示例：
nums = [3,1,5,8]，加边界1后val = [1,3,1,5,8,1]
dp[0][5] = max( dp[0][1] + dp[1][5] + 1*3*1, dp[0][2] + dp[2][5] + 1*1*1, dp[0][3] + dp[3][5] + 1*5*1, dp[0][4] + dp[4][5] + 1*8*1 )
代码实现：
class Solution { public: int maxCoins(vector<int>& nums) { int n = nums.size(); vector<int> val(n + 2, 1); for (int i = 0; i < n; i++) { val[i + 1] = nums[i]; } // dp[i][j] 表示戳破开区间 (i, j) 内所有气球的最大收益 vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0)); // 按区间长度递增遍历 for (int len = 2; len <= n + 1; len++) { for (int i = 0; i + len <= n + 1; i++) { int j = i + len; // 枚举最后一个戳破的气球 k 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]; } };复杂度分析：
设n是气球数量。
| 维度 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n³) | 三重循环：区间长度 × 起点 × 分割点 |
| 空间复杂度 | O(n²) | dp 数组 |
关键细节：
1. 为什么加虚拟边界1？
处理i-1或i+1越界的情况，统一为1，简化边界判断。
2. 为什么用开区间(i, j)？
因为dp[i][j]表示戳破i和j之间的气球，i和j本身不戳破。这样i和j可以作为边界参与乘积计算。
3. 为什么枚举"最后一个戳破"？
因为正向枚举"第一个戳破"会导致左右子问题不独立。反向枚举"最后一个戳破"，左右子问题完全独立。
4. 遍历顺序
必须按区间长度递增遍历，因为dp[i][j]依赖更小的区间dp[i][k]和dp[k][j]。
5. 和「矩阵链乘法」的区别
| 题目 | 区别 |
|---|---|
| 312. 戳气球 | 乘积收益 |
| 矩阵链乘法 | 乘积代价 |
本质都是区间 DP，状态转移类似。
方法二：记忆化搜索
代码实现：
class Solution { public: int maxCoins(vector<int>& nums) { int n = nums.size(); vector<int> val(n + 2, 1); for (int i = 0; i < n; i++) val[i + 1] = nums[i]; vector<vector<int>> memo(n + 2, vector<int>(n + 2, -1)); return dfs(val, 0, n + 1, memo); } private: int dfs(vector<int>& val, int i, int j, vector<vector<int>>& memo) { if (i + 1 == j) return 0; // 区间内没有气球 if (memo[i][j] != -1) return memo[i][j]; int result = 0; for (int k = i + 1; k < j; k++) { result = max(result, dfs(val, i, k, memo) + dfs(val, k, j, memo) + val[i] * val[k] * val[j]); } memo[i][j] = result; return result; } };复杂度：时间 O(n³)，空间 O(n²)
两种方法对比：
| 方法 | 时间复杂度 | 空间复杂度 | 推荐度 |
|---|---|---|---|
| 区间 DP | O(n³) | O(n²) | ⭐⭐⭐⭐⭐ |
| 记忆化搜索 | O(n³) | O(n²) | ⭐⭐⭐⭐ |
总结：
| 要点 | 说明 |
|---|---|
| 核心思想 | 反向思考，枚举最后一个戳破的气球 |
| 状态定义 | dp[i][j]戳破开区间(i,j)的最大收益 |
| 状态转移 | dp[i][j] = max(dp[i][k] + dp[k][j] + val[i]*val[k]*val[j]) |
| 时间复杂度 | O(n³) |
| 空间复杂度 | O(n²) |
