戳气球：逆向区间 DP

给定 n 个数值存储在 nums 中的气球，戳破气球 i 可获得 nums[i-1] * nums[i] * nums[i+1] 枚硬币（即自身与当前相邻气球的乘积）。气球戳破后，其相邻气球会变成相邻的气球。请找出戳破所有气球后能够获得的最大硬币数。朴素模拟很难处理这个问题，因为戳破气球会改变相邻关系——逆向区间 DP 可以巧妙地绕开这一困难。

如果我们尝试将 dp[i][j] 定义为戳破范围 [i, j] 内气球所能获得的最大硬币数，并思考应该先戳破哪个气球，就会遇到一个问题：如果先戳破气球 k，则 nums[k-1] 和 nums[k+1] 必须是当前相邻气球——但这些气球可能之后才会被戳破，从而动态改变相邻关系。在正向处理中，很难清晰地定义状态。

关键技巧是思考区间 [i, j] 中最后被戳破的是哪个气球。当气球 k 是 [i, j] 中最后被戳破的气球时，该区间中的其他气球都已经消失。因此，气球 k 的相邻气球恰好是 nums[i-1] 和 nums[j+1]——即区间外侧紧邻边界的气球。这样，最后一次戳破所获得的硬币数就是确定的：它不依赖于之前戳破气球的顺序。

添加哨兵气球：在 nums 的开头和末尾各添加 1，形成 nums = [1] + nums + [1]。将 dp[i][j] 定义为戳破索引 i 和 j 之间所有气球（不包含端点）所能获得的最大硬币数，其中 nums[i] 和 nums[j] 是保留下来的边界气球。递推关系：对于 (i, j) 中每个候选的最后一个气球 k：dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j])。

我们用哨兵填充数组，将 DP 表初始化为零（空区间 = 0 枚硬币），并按区间长度递增的顺序填充。最终答案是 dp[0][n+1]，表示在哨兵作为永久边界的情况下，戳破所有原始气球所能获得的最大硬币数。

对于 [3, 1, 5, 8]，填充哨兵后变为 [1, 3, 1, 5, 8, 1]（索引为 0-5）。我们要求的是 dp[0][5]。对于长度为 2 的区间（内部包含一个气球）：dp[0][2] = 1*3*1=3、dp[1][3]=3*1*5=15、dp[2][4]=1*5*8=40、dp[3][5]=5*8*1=40。逐步构建后，最优方案是在先戳破 {3,1,5,8} 中其他气球的相邻气球后，最后戳破 1，总共获得 167 枚硬币。

共有 O(n²) 个区间，每个区间尝试 O(n) 个分割点，因此时间复杂度为 O(n³)。DP 表的空间复杂度为 O(n²)。当 n = 500 个气球时，需要进行 1.25 亿次操作，这在面试限制下是可行的。使用哨兵填充可以简化边界处理：如果没有哨兵，就需要明确检查 i-1 和 j+1 是否在有效范围内。

同一个解法也可以使用 @lru_cache 以自顶向下的方式编写，这在面试中推导时可能更加直观。将 solve(i, j) 定义为开区间 (i, j) 中的最大硬币数。该函数尝试所有可能的 k 作为最后被戳破的气球，并将结果记忆化。两种方法具有相同的时间和空间复杂度。

一个常见错误是将 dp[i][j] 定义为戳破 [i,j] 中第一个气球时获得的硬币数，而不是最后一个。这样做会失败，因为第一次戳破所获得的硬币数取决于尚未被戳破的相邻气球——而这些相邻气球的状态会随着算法推进而改变。当边界取决于仍然存在的元素时，请始终在区间 DP 中思考最后一个元素。

选择值为 1 的哨兵，是因为它们在乘法中充当中性元素。当边界气球最后被戳破时，其硬币数为 boundary * last * boundary = 1 * last * 1 = last。使用 0 会得到 0 枚硬币（这是错误的），使用其他值则会扭曲计算结果。哨兵技巧可以统一处理所有边界情况，而不必为最左侧和最右侧气球编写特殊逻辑。

在标准区间 DP（矩阵链乘法）中，分割点 k 表示将问题划分为两个独立求解的子问题的位置。在戳气球问题中，k 是区间中最后被戳破的气球；在 k 仍作为边界存在的前提下，两个子区间 [i,k] 和 [k,j] 可以独立求解。这种逆向视角正是让戳气球问题能够使用区间 DP 解决的巧妙思路。

测试您对本课数据结构 & 算法 — 编程面试准备相关概念的理解。

本课您学习了：正向模拟会失败，因为引爆气球会不可预测地改变相邻元素，逆向思路将 k 定义为区间内最后被引爆的气球，使相邻元素成为 nums[i] 和 nums[j]，以及使用哨兵填充的递推式 dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]) 可以得到 O(n³) 解法。接下来我们将转向背包 DP，从经典的 0/1 背包及其空间优化开始。