戳气球问题（二维DP解法优化） 题目描述 给定 n 个气球，每个气球上标有一个数字，这些数字存储在数组 nums 中。现在你需要戳破所有气球。戳破第 i 个气球时，你可以获得 nums[left] * nums[i] * nums[right] 枚硬币，其中 left 和 right 是与 i 相邻的气球的下标。戳破 i 后， left 和 right 就变成相邻的气球。求你能获得的最大硬币数量。 示例 输入： nums = [3,1,5,8] 输出： 167 解释： nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> [] 获得硬币： 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167 （注意：戳破最后一个气球时，左右相邻视为数字 1 的虚拟气球） 解题步骤 1. 问题转化 原数组 nums 长度为 n，我们可以在首尾各添加一个数字 1 作为边界，得到长度 n+2 的新数组 a ，其中 a[0] = a[n+1] = 1 ， a[1..n] 为原 nums 。 这样，问题转化为：戳破 a[1..n] 的所有气球，求最大得分，且 a[0] 和 a[n+1] 永不戳破。 2. DP 状态定义 定义 dp[i][j] 表示戳破区间 (i, j) 内（ 不包含 i 和 j 本身）所有气球能获得的最大硬币数，其中 0 ≤ i < j ≤ n+1 。 最终答案是 dp[0][n+1] ，即戳破 (0, n+1) 内的所有气球（即原数组所有气球）。 3. 状态转移思路 对于区间 (i, j) ，考虑 最后一个被戳破的气球 k （ i < k < j ）。 由于 k 是最后一个戳破的，此时区间内其他气球都已消失，所以 k 的左右相邻气球就是 i 和 j。 戳破 k 获得的硬币是 a[i] * a[k] * a[j] 。 在戳破 k 之前，我们已经获得了戳破 (i, k) 和 (k, j) 区间内所有气球的硬币，即 dp[i][k] + dp[k][j] 。 因此，状态转移方程为： dp[i][j] = max(dp[i][k] + dp[k][j] + a[i]*a[k]*a[j]) ，其中 k 在 (i, j) 之间遍历。 4. DP 计算顺序 由于 dp[i][j] 依赖于更短的区间 dp[i][k] 和 dp[k][j] ，我们按区间长度 len 从小到大计算。 len 从 2 开始（因为区间至少包含一个气球，即 j-i >= 2 ），直到 len = n+1 。 5. 示例推演 以 nums = [3,1,5,8] 为例： 扩展数组 a = [1,3,1,5,8,1] ，n=4。 初始化：所有 dp[i][j] = 0 。 len=2 ：区间 (0,2) 只有气球 1（对应原 3）， dp[0][2] = a[0]*a[1]*a[2] = 1*3*1 = 3 。 同理计算其他长度为 2 的区间。 len=3 ：例如区间 (0,3)： k=1: dp[0][1]+dp[1][3]+a[0]*a[1]*a[3]=0+0+1*3*5=15 k=2: dp[0][2]+dp[2][3]+a[0]*a[2]*a[3]=3+0+1*1*5=8 取最大值 15 为 dp[0][3] 。 继续计算直到 dp[0][5] 即为结果 167。 6. 算法实现要点 时间复杂度 O(n³)，空间复杂度 O(n²)。 注意：此解法是“倒着想”的逆向思维（先定最后戳破的气球），避免了区间合并时依赖顺序的问题。 7. 核心思想总结 通过添加边界 1 简化问题。 定义 dp[i][j] 为开区间最大得分，避免气球戳破后的相邻关系混乱。 逆向思考，枚举区间内最后一个戳破的气球，将问题分解为两个独立子区间。