戳气球获得最大分数问题（基础版本）
字数 2547 2025-12-10 05:49:28

戳气球获得最大分数问题（基础版本）

问题描述

给定一个包含 n 个气球的数组 nums，每个气球上标有一个数字。你需要戳破所有的气球。戳破第 i 个气球时，你可以获得 nums[left] * nums[i] * nums[right] 的分数。这里的 left 和 right 是第 i 个气球相邻的、尚未被戳破的气球序号。如果戳破的气球在边界上，那么缺失的相邻气球视为数字 1。
你的目标是找到戳破所有气球能获得的最大总分数。

示例：

  • 输入：nums = [3,1,5,8]
  • 输出：167
  • 解释：
    • 一种最优戳破顺序：1, 5, 3, 8。
    • 第一步戳破 nums[1]=1，得分 = 3*1*5 = 15，数组变为 [3,5,8]。
    • 第二步戳破 nums[1]=5，得分 = 3*5*8 = 120，数组变为 [3,8]。
    • 第三步戳破 nums[0]=3，得分 = 1*3*8 = 24，数组变为 [8]。
    • 第四步戳破 nums[0]=8，得分 = 1*8*1 = 8。
    • 总得分 = 15 + 120 + 24 + 8 = 167。

解题思路（区间动态规划）

这个问题的一个关键观察是：最后被戳破的气球决定了其左右两部分的独立计算。我们可以逆向思考：考虑某个区间内最后一个被戳破的气球，那么它左边和右边的区间是独立的，并且它在被戳破时，其左右邻居是区间外的气球（或者边界外的虚拟气球 1）。

1. 定义状态

  • 在原数组首尾各添加一个值为 1 的虚拟气球，形成新数组 a，长度 n+2。这样处理边界更方便（因为任何气球被戳破时，其左右邻居至少是 1）。
  • 定义 dp[i][j]：表示戳破开区间 (i, j) 内（即下标从 i+1 到 j-1）所有气球能获得的最大分数。
  • 我们的目标是求 dp[0][n+1]，即戳破原所有气球（整个开区间 (0, n+1)）的最大分数。

2. 状态转移

  • 对于区间 (i, j)，我们考虑在这个区间内最后戳破的气球 k（i < k < j）。
  • 为什么是最后戳破？因为当 k 是区间内最后一个被戳破的气球时，此时区间 (i, j) 内只有 k 还没破，其左右邻居就是区间外的 i 和 j 位置的气球。所以戳破 k 的得分是 a[i] * a[k] * a[j]。
  • 在戳破 k 之前，区间 (i, k) 和 (k, j) 内的气球已经全部被戳破了。由于它们是独立的，其最大分数分别为 dp[i][k] 和 dp[k][j]。
  • 因此，如果我们选择 k 作为最后戳破的气球，那么区间 (i, j) 的总得分为： 
    dp[i][j] = max(dp[i][k] + dp[k][j] + a[i] * a[k] * a[j])，其中 k 遍历 (i, j) 内的所有气球。

3. 计算顺序

  • 区间动态规划通常按区间长度从小到大的顺序计算。
  • 先计算长度最小的区间（即区间内只有一个气球），再逐步扩大区间长度。
  • 具体来说：
    • 区间长度 len 从 2 开始（因为开区间 (i, j) 至少需要包含一个气球，即 j - i >= 2），最大到 n+2（整个数组）。
    • 对于每个长度 len，枚举所有可能的左端点 i，右端点 j = i + len。
    • 然后遍历所有可能的最后戳破的气球 k（i < k < j），更新 dp[i][j]。

4. 初始化和边界

  • 初始化：dp[i][j] = 0（当区间内没有气球时，得分为 0）。
  • 按照上述顺序计算即可。

示例推导（nums = [3,1,5,8]）

  1. 扩展数组：a = [1, 3, 1, 5, 8, 1]（长度 6，原索引 1~4 对应原数组）。
  2. 计算 dp[i][j]（0 <= i < j <= 5）：
    • len=2：区间内无气球，dp[i][i+2] 直接为 0（实际上不会用到，因为至少需要 len>=3 才有一个气球，但按定义 len=2 时 j-i=2，开区间内无气球，得分 0）。
    • len=3：区间内只有一个气球 k=i+1。
      • 例如 (0,2)：气球 k=1（原 3），得分 = a[0]*a[1]*a[2] = 1*3*1 = 3。
      • (1,3)：气球 k=2（原 1），得分 = a[1]*a[2]*a[3] = 3*1*5 = 15。
      • (2,4)：气球 k=3（原 5），得分 = a[2]*a[3]*a[4] = 1*5*8 = 40。
      • (3,5)：气球 k=4（原 8），得分 = a[3]*a[4]*a[5] = 5*8*1 = 40。
    • len=4：区间内有两个气球，需要枚举最后戳破哪个。
      • 例如 (0,3)：气球 k=1 或 k=2。
        • k=1：得分 = dp[0][1] + dp[1][3] + a[0]*a[1]*a[3] = 0 + 15 + 1*3*5 = 30。
        • k=2：得分 = dp[0][2] + dp[2][3] + a[0]*a[2]*a[3] = 3 + 0 + 1*1*5 = 8。
        • 取最大值 30，即 dp[0][3]=30。
    • 以此类推，最终计算 dp[0][5]（即整个区间）：
      • 需要枚举最后戳破的气球 k=1,2,3,4。
      • 例如 k=2（原气球 1）：
        • 得分 = dp[0][2] + dp[2][5] + a[0]*a[2]*a[5] = 3 + 48 + 1*1*1 = 52（其中 dp[2][5] 需要提前计算）。
      • 经过计算，最大值为 167。

算法复杂度

  • 时间复杂度：O(n³)，需要三重循环（区间长度、左端点、分割点）。
  • 空间复杂度：O(n²)，用于存储 dp 表。

总结

这个问题的核心是逆向思维：从最后一个被戳破的气球入手，将问题分解为左右两个独立子区间。通过区间动态规划，自底向上计算所有小区间的最优解，最终得到整个区间的最大分数。注意添加虚拟气球 1 以简化边界处理。

戳气球获得最大分数问题（基础版本） 问题描述 给定一个包含 n 个气球的数组 nums ，每个气球上标有一个数字。你需要戳破所有的气球。戳破第 i 个气球时，你可以获得 nums[left] * nums[i] * nums[right] 的分数。这里的 left 和 right 是第 i 个气球相邻的、尚未被戳破的气球序号。如果戳破的气球在边界上，那么缺失的相邻气球视为数字 1 。 你的目标是找到戳破所有气球能获得的 最大总分数 。 示例： 输入： nums = [3,1,5,8] 输出： 167 解释： 一种最优戳破顺序： 1, 5, 3, 8 。 第一步戳破 nums[1]=1 ，得分 = 3*1*5 = 15 ，数组变为 [3,5,8] 。 第二步戳破 nums[1]=5 ，得分 = 3*5*8 = 120 ，数组变为 [3,8] 。 第三步戳破 nums[0]=3 ，得分 = 1*3*8 = 24 ，数组变为 [8] 。 第四步戳破 nums[0]=8 ，得分 = 1*8*1 = 8 。 总得分 = 15 + 120 + 24 + 8 = 167 。 解题思路（区间动态规划） 这个问题的一个关键观察是： 最后被戳破的气球决定了其左右两部分的独立计算 。我们可以逆向思考：考虑某个区间内最后一个被戳破的气球，那么它左边和右边的区间是独立的，并且它在被戳破时，其左右邻居是区间外的气球（或者边界外的虚拟气球 1 ）。 1. 定义状态 在原数组首尾各添加一个值为 1 的虚拟气球，形成新数组 a ，长度 n+2 。这样处理边界更方便（因为任何气球被戳破时，其左右邻居至少是 1 ）。 定义 dp[i][j] ：表示戳破开区间 (i, j) 内（即下标从 i+1 到 j-1 ）所有气球能获得的最大分数。 我们的目标是求 dp[0][n+1] ，即戳破原所有气球（整个开区间 (0, n+1) ）的最大分数。 2. 状态转移 对于区间 (i, j) ，我们考虑在这个区间内 最后戳破的气球 k （ i < k < j ）。 为什么是最后戳破？因为当 k 是区间内最后一个被戳破的气球时，此时区间 (i, j) 内只有 k 还没破，其左右邻居就是区间外的 i 和 j 位置的气球。所以戳破 k 的得分是 a[i] * a[k] * a[j] 。 在戳破 k 之前，区间 (i, k) 和 (k, j) 内的气球已经全部被戳破了。由于它们是独立的，其最大分数分别为 dp[i][k] 和 dp[k][j] 。 因此，如果我们选择 k 作为最后戳破的气球，那么区间 (i, j) 的总得分为： 3. 计算顺序 区间动态规划通常按 区间长度 从小到大的顺序计算。 先计算长度最小的区间（即区间内只有一个气球），再逐步扩大区间长度。 具体来说： 区间长度 len 从 2 开始（因为开区间 (i, j) 至少需要包含一个气球，即 j - i >= 2 ），最大到 n+2 （整个数组）。 对于每个长度 len ，枚举所有可能的左端点 i ，右端点 j = i + len 。 然后遍历所有可能的最后戳破的气球 k （ i < k < j ），更新 dp[i][j] 。 4. 初始化和边界 初始化： dp[i][j] = 0 （当区间内没有气球时，得分为 0 ）。 按照上述顺序计算即可。 示例推导（ nums = [3,1,5,8] ） 扩展数组： a = [1, 3, 1, 5, 8, 1] （长度 6 ，原索引 1~4 对应原数组）。 计算 dp[i][j] （ 0 <= i < j <= 5 ）： len=2 ：区间内无气球， dp[i][i+2] 直接为 0 （实际上不会用到，因为至少需要 len>=3 才有一个气球，但按定义 len=2 时 j-i=2 ，开区间内无气球，得分 0 ）。 len=3 ：区间内只有一个气球 k=i+1 。 例如 (0,2) ：气球 k=1 （原 3 ），得分 = a[0]*a[1]*a[2] = 1*3*1 = 3 。 (1,3) ：气球 k=2 （原 1 ），得分 = a[1]*a[2]*a[3] = 3*1*5 = 15 。 (2,4) ：气球 k=3 （原 5 ），得分 = a[2]*a[3]*a[4] = 1*5*8 = 40 。 (3,5) ：气球 k=4 （原 8 ），得分 = a[3]*a[4]*a[5] = 5*8*1 = 40 。 len=4 ：区间内有两个气球，需要枚举最后戳破哪个。 例如 (0,3) ：气球 k=1 或 k=2 。 k=1 ：得分 = dp[0][1] + dp[1][3] + a[0]*a[1]*a[3] = 0 + 15 + 1*3*5 = 30 。 k=2 ：得分 = dp[0][2] + dp[2][3] + a[0]*a[2]*a[3] = 3 + 0 + 1*1*5 = 8 。 取最大值 30 ，即 dp[0][3]=30 。 以此类推，最终计算 dp[0][5] （即整个区间）： 需要枚举最后戳破的气球 k=1,2,3,4 。 例如 k=2 （原气球 1 ）： 得分 = dp[0][2] + dp[2][5] + a[0]*a[2]*a[5] = 3 + 48 + 1*1*1 = 52 （其中 dp[2][5] 需要提前计算）。 经过计算，最大值为 167 。 算法复杂度 时间复杂度： O(n³) ，需要三重循环（区间长度、左端点、分割点）。 空间复杂度： O(n²) ，用于存储 dp 表。 总结 这个问题的核心是逆向思维：从最后一个被戳破的气球入手，将问题分解为左右两个独立子区间。通过区间动态规划，自底向上计算所有小区间的最优解，最终得到整个区间的最大分数。注意添加虚拟气球 1 以简化边界处理。