0312. 戳气球

题目地址（312. 戳气球）

https://leetcode-cn.com/problems/burst-balloons/

题目描述

有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。每当你戳破一个气球 i 时，你可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。

求所能获得硬币的最大数量。

说明:

你可以假设 nums[-1] = nums[n] = 1，但注意它们不是真实存在的所以并不能被戳破。
0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
示例:

输入: [3,1,5,8]
输出: 167
解释: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
     coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

前置知识

• 回溯法

• 动态规划

公司

• 阿里

• 腾讯

• 百度

• 字节

回溯法（超时）

回溯法

这道题就是要戳破所有的气球，求获得硬币的最大数量。我的第一反应就是暴力回溯。

但是这种暴力算法肯定会超时，为什么呢？因为题目给的气球数量有点多，最多 500 个；500 的阶乘，会超时爆栈；但是我们依然写一下代码，找下突破口，小伙伴们千万不要看不起暴力，暴力是优化的突破口；

如果小伙伴对回溯法不太熟悉，我建议你记住下面的模版，也可以看我之前写的文章，回溯法基本可以使用以下的模版写。

代码

var maxCoins = function (nums) {
  let res = Number.MIN_VALUE;
  backtrack(nums, 0);
  return res;
  // 回溯法，状态树很大
  function backtrack(nums, score) {
    if (nums.length == 0) {
      res = Math.max(res, score);
      return;
    }
    for (let i = 0, n = nums.length; i < n; i++) {
      let point =
        (i - 1 < 0 ? 1 : nums[i - 1]) *
        nums[i] *
        (i + 1 >= n ? 1 : nums[i + 1]);
      let tempNums = [].concat(nums);
      // 做选择 在 nums 中删除元素 nums[i]
      nums.splice(i, 1);
      // 递归回溯
      backtrack(nums, score + point);
      // 撤销选择
      nums = [...tempNums];
    }
  }
};

动态规划

思路

回溯法的缺点也很明显，复杂度很高，小伙伴们可以脑补一下执行过程的状态树，这里我偷个懒就不画了；

通过仔细观察这个状态树，我们会发现这个状态树的【选择】上，会有一些重复的选择分支；很明显存在了重复子问题；自然我就想到了能不能用动态规划来解决；

判读能不能用动态规划解决，还有一个问题，就是必须存在最优子结构；什么意思呢？其实就是根据局部最优，推导出答案；假设我们戳破第 k 个气球是最优策略的最后一步，和上一步有没有联系呢？根据题目意思，戳破第 k 个，前一个和后一个就变成相邻的了。由于这种不稳定性，导致问题难以处理。一种解决方案是反向思考。即我们不是给你一个 nums，一个个移除数。而是从空数组开始一个个添加。

由于题目说明了 nums 左右各存在一个虚拟的气球，因此这里说的空数组实际指的是 [1,1] 这种情况，即只有两个虚拟数字。

经过这样的反向思考，问题就变得简单起来了。经过这样的思考之后就使用动态规划解决就 ok 了。

既然用动态规划，那就老套路了，把动态规划的三个问题想清楚定义好；然后找出题目的【状态】和【选择】，然后根据【状态】枚举，枚举的过程中根据【选择】计算递推就能得到答案了。

那本题的【选择】是什么呢？就是戳哪一个气球。那【状态】呢？就是题目给的气球数量。

1. 定义状态

这里有个细节，就是题目说明有两个虚拟气球，nums[-1] = nums[n] = 1；如果当前戳破的气球是最后一个或者第一个，前面/后面没有气球了，不能乘以 0，而是乘以 1。

定义状态的最关键两个点，往子问题（问题规模变小）想，最后一步最优策略是什么；我们假设最后戳破的气球是 k，戳破 k 获得最大数量的银币就是 nums[i] * nums[k] * nums[j] 再加上前面戳破的最大数量和后面的最大数量，即：nums[i] * nums[k] * nums[j] + 前面最大数量 + 后面最大数量。

那我们可以这样来定义状态，dp[i][j] = x 表示：戳破气球 i 和气球 j 之间（开区间，不包括 i 和 j）的所有气球，可以获得的最大硬币数为 x。为什么开区间？因为不能和已经计算过的产生联系，我们这样定义之后，利用两个虚拟气球 就可完成本题。

1. 状态转移方程

而对于 dp[i][j]，i 和 j 之间会有很多气球，到底该戳哪个先呢？我们直接设为 k，枚举选择最优的 k 就可以了。所以，最终的状态转移方程为：dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + nums[k] * nums[i] * nums[j])。由于是开区间，因此 k 为 i + 1, i + 2... j - 1。

这就是典型的枚举分割点 ”区间 DP“，大家一定要掌握哦~

1. 初始值和边界

由于我们利用了两个虚拟气球，边界就是气球数 n + 2，当 i == j 时，很明显两个之间没有气球，为 0；

1. 如何枚举状态

因为我们最终要求的答案是 dp[0][n + 1]，就是戳破虚拟气球之间的所有气球获得的最大值。当 i == j 时，i 和 j 之间是没有气球的，所以枚举的状态很明显是 dp table 的左上部分，也就是 j 大于 i，如下图所示，只给出一部分方便思考。

图有错误。图中 dp[k][i] 应该是 dp[i][k]，dp[j][k] 应该是 dp[k][j]

从上图可以看出，我们需要从下到上，从左到右进行遍历。

关键点

• 区间 DP

• 反向思考。不是戳气球，而是添加气球。

• 遍历方向的确定

代码

代码支持： JS, Python

JS Code:

var maxCoins = function (nums) {
  let n = nums.length;
  // 添加两侧的虚拟气球
  let points = [1, ...nums, 1];
  let dp = Array.from(Array(n + 2), () => Array(n + 2).fill(0));
  // 最后一行开始遍历,从下往上
  for (let i = n; i >= 0; i--) {
    // 从左往右
    for (let j = i + 1; j < n + 2; j++) {
      for (let k = i + 1; k < j; k++) {
        dp[i][j] = Math.max(
          dp[i][j],
          points[j] * points[k] * points[i] + dp[i][k] + dp[k][j]
        );
      }
    }
  }
  return dp[0][n + 1];
};

Python Code:

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        n = len(nums)
        points = [1] + nums + [1]
        dp = [[0] * (n + 2) for _ in range(n + 2)]

        for i in range(n, -1, -1):
            for j in range(i + 1, n + 2):
                for k in range(i + 1, j):
                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + points[i] * points[k] * points[j])
        return dp[0][-1]

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n ^ 3)$

• 空间复杂度：$O(n ^ 2)$

如果使用记忆化递归，时间复杂度和上面一样，空间复杂度是 $O(n)$，但是在力扣提交会超时，大家作为参考即可。

Python3 Code:

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        n = len(nums)
        nums = [1] + nums + [1]

        @lru_cache(None)
        def dp(left, right):
            if left + 1 == right:
                return 0
            if left + 2 == right:
                return nums[left] * nums[left + 1] * nums[left + 2]
            ans = 0
            for i in range(left + 1, right):
                ans = max(ans, nums[i] * nums[left] * nums[right] + dp(left, i) + dp(i, right))
            return ans

        return dp(0, len(nums) - 1)

相关题目

• Maximum-Additive-Score-by-Removing-Numbers

总结

简单的 dp 题目会直接告诉你怎么定义状态，告诉你怎么选择计算，你只需要根据套路判断一下能不能用 dp 解题即可，而判断能不能，往往暴力就是突破口。

这道题如果从空数组反向思考，则避免了因为数组变化导致的状态变化而难以处理的问题，是一种常见的技巧。另外此题属于典型的分割 DP 问题。区间问题通常都是两层循环枚举所有的左右端点，再用一层循环枚举所有的割点，也就是三层循环，时间复杂度也是 $O(n^3)$。

更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 30K star 啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。