戳气球问题（状态转移优化版本）

题目描述
有一排气球，每个气球上标有一个正整数。你需要戳破所有气球，获得最大分数。
规则：

1. 戳破第 \(i\) 个气球时，获得的分数为 nums[left] * nums[i] * nums[right]，其中 left 和 right 是当前未被戳破的气球中，紧邻第 \(i\) 个气球的左、右气球（如果左/右没有未被戳破的气球，则对应值视为 1）。
2. 戳破后，气球被移除，左右气球会相邻。

示例
输入：nums = [3,1,5,8]
输出：167
解释：
戳破顺序（最优）：

1. 戳 1 → 得分 = 3×1×5 = 15，剩下 [3,5,8]
2. 戳 5 → 得分 = 3×5×8 = 120，剩下 [3,8]
3. 戳 3 → 得分 = 1×3×8 = 24，剩下 [8]
4. 戳 8 → 得分 = 1×8×1 = 8
   总得分 = 15 + 120 + 24 + 8 = 167

解题思路

• 如果按顺序戳气球，左右会变化，难以直接规划。
• 逆向思考：考虑最后戳破的气球，它能确定获得其值乘“边界”的值。
• 定义 dp[i][j] 为区间 (i, j) 内（开区间，即不包括 i 和 j 本身）所有气球被戳破能获得的最大分数，边界 i 和 j 视为虚拟气球（值为 1）。
• 状态转移：在 (i, j) 中，选择某个位置 k 作为最后戳破的气球，则：

  dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j])
  

  其中 k ∈ (i, j)，nums[i] 和 nums[j] 是当前区间外的左右边界值。

详细步骤

1. 在数组首尾各添加一个 1，方便处理边界，新数组为 a，长度为 n+2。
2. 定义 dp[i][j] 为区间 (i, j) 的最大得分，i < j，且区间内至少有一个气球（即 j ≥ i+2）。
3. 从小到大枚举区间长度 len 从 2 到 n+1（因为开区间长度至少为 3 才有气球，但 len 表示索引跨度）。
   • 对于每个起点 i，终点 j = i + len。
   • 枚举区间内最后一个戳破的气球位置 k ∈ (i, j)。
   • 状态转移：
     dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + a[i] * a[k] * a[j])
4. 最终答案在 dp[0][n+1]。

举例说明（nums = [3,1,5,8]）

1. 扩展数组 a = [1,3,1,5,8,1]。
2. len=2 时，区间长度只有 1 个气球（如 (0,2) 只有气球 1 在位置 1）：
   • (0,2)：k=1，得分 = 0 + 0 + 1×3×1 = 3。
3. len=3 时，区间有 2 个气球（如 (0,3) 有位置 1,2）：
   • 对 (0,3)：
     k=1：得分 = dp[0][1]+dp[1][3]+1×3×5 = 0+0+15=15。
     k=2：得分 = dp[0][2]+dp[2][3]+1×1×5 = 3+0+5=8，取 max=15。
4. 继续直到 len=5（即区间 (0,5) 包含所有气球），计算得 167。

时间复杂度：O(n³)（三重循环），空间 O(n²)。
优化思路：此版本已是标准 DP 解法，但可注意循环顺序，让小区间先计算。

关键点

• 开区间定义避免边界干扰。
• 逆向思考“最后戳破”的气球，从而固定左右边界值。
• 状态转移时，左右子问题独立，因为 k 最后戳破，所以左右区间被分开。