戳气球问题 题目描述 给定一组气球，每个气球上标有一个数字。这些数字存储在一个数组 nums 中，其中 nums[i] 表示第 i 个气球上的数字。你的任务是戳破所有气球，以获取最大数量的硬币。规则如下： 当你戳破一个气球 i 时，你可以获得 nums[left] * nums[i] * nums[right] 个硬币。 戳破气球 i 后， left 和 right 气球会变成相邻的气球。 如果 i 是边界气球（即 left 或 right 超出数组边界），则乘以虚拟数字 1 。 例如，对于 nums = [3, 1, 5, 8] ，戳破所有气球能获得的最大硬币数是多少？ 解题思路 问题分析 如果按顺序戳气球，每次戳破后数组会变化，难以直接规划。 关键思路：逆向思考！将“戳破气球”改为“添加气球”。即考虑在区间内最后一个被戳破的气球，此时它左右两边的气球是区间外的边界。 状态定义 在数组首尾添加虚拟气球，值为 1 ，形成新数组 vals ，长度为 n+2 。 定义 dp[i][j] 表示开区间 (i, j) 内（即不戳破 i 和 j ）能获得的最大硬币数。 目标：求 dp[0][n+1] 。 状态转移方程 在区间 (i, j) 中，枚举最后一个被戳破的气球 k （ i < k < j ）。 戳破 k 时，左右边界是 vals[i] 和 vals[j] ，获得的硬币为 vals[i] * vals[k] * vals[j] 。 戳破 k 前，需要先戳破 (i, k) 和 (k, j) 内的气球，因此： \[ dp[ i][ j] = \max_ {i < k < j} \left( dp[ i][ k] + dp[ k][ j] + vals[ i] \cdot vals[ k] \cdot vals[ j ] \right) \] 计算顺序 区间长度 len 从 2 到 n+1 （因为区间至少包含一个气球）。 对每个区间起点 i ，计算终点 j = i + len 。 枚举区间内的所有 k 进行状态转移。 示例演示 （ nums = [3, 1, 5, 8] ） 扩展数组： vals = [1, 3, 1, 5, 8, 1] 。 区间长度 len=3 时，计算 dp[0][2] （即区间 (0,2) ，包含气球 1 ）： 唯一选择 k=1 ，硬币数 vals[0]*vals[1]*vals[2] = 1*3*1 = 3 。 最终计算 dp[0][5] ，得到最大硬币数 167 。 总结 核心思想：逆向处理，将最后一个戳破的气球作为分割点。 时间复杂度：O(n³)，空间复杂度：O(n²)。 关键点：定义开区间 (i, j) 避免重复计算，并保证边界气球始终存在。