题目描述有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)内最后一个被戳破的气球kdp[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(vectorint nums) { int n nums.size(); vectorint val(n 2, 1); for (int i 0; i n; i) { val[i 1] nums[i]; } // dp[i][j] 表示戳破开区间 (i, j) 内所有气球的最大收益 vectorvectorint dp(n 2, vectorint(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或i1越界的情况统一为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(vectorint nums) { int n nums.size(); vectorint val(n 2, 1); for (int i 0; i n; i) val[i 1] nums[i]; vectorvectorint memo(n 2, vectorint(n 2, -1)); return dfs(val, 0, n 1, memo); } private: int dfs(vectorint val, int i, int j, vectorvectorint 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²)两种方法对比方法时间复杂度空间复杂度推荐度区间 DPO(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²)