题目描述：

有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是气球数量。

关键细节：

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. 和「矩阵链乘法」的区别

本质都是区间 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²)

两种方法对比：

总结：