# 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 的阶乘，会超时爆栈；但是我们依然写一下代码，找下突破口，小伙伴们千万不要看不起暴力，暴力是优化的突破口；

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

#### 代码

```js
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，如下图所示，只给出一部分方便思考。

![](https://p.ipic.vip/8ugnau.jpg)

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

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

#### 关键点

* 区间 DP
* 反向思考。不是戳气球，而是添加气球。
* 遍历方向的确定

#### 代码

代码支持： JS, Python

JS Code:

```js
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:

```py
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:

```py
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](https://binarysearch.com/problems/Maximum-Additive-Score-by-Removing-Numbers)

### 总结

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

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

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

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/312.burst-balloons.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.