# \[312]\[困难]\[分治]\[递归]\[动态规划] 戳气球

## 题目描述

[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
```

## 解题思路

[戳气球](https://leetcode-cn.com/problems/burst-balloons/solution/chuo-qi-qiu-by-leetcode-solution/)

### 分治递归

为了方便处理，我们对 `nums` 数组稍作处理，将其两边各加上题目中假设存在的 `nums[−1]` 和 `nums[n]` ，并保存在 `val` 数组中，即 `val[i]=nums[i−1]` 。之所以这样处理是为了处理 `nums[−1]` ，防止下标越界。

下文中的区间均指数组 `val` 上的区间。

我们观察戳气球的操作，发现这会导致两个气球从不相邻变成相邻，使得后续操作难以处理。**于是我们倒过来看这些操作，将全过程看作是每次添加一个气球。** 在区间中插入一个气球, 等价于在这个区间中最后一个戳爆这个气球, 但这种转变让我们有了递归的思路: 插入一个气球后, 我们以这个气球为边界, 将原来的区间划分成了左右两个子区间, 最终的数量等于两个区间的数量再加上这个气球对应的数量. 然后左右子区间递归计算.

我们定义方法 `solve`，令 `solve(i,j)` 表示将开区间 `(i,j)` 内的位置全部填满气球能够得到的最多硬币数。由于是开区间，因此区间两端的气球的编号就是 `i` 和 `j`，对应着 `val[i]` 和 `val[j]`。

* 当 `i >= j - 1`时，开区间中没有气球，`solve(i,j)` 的值为 0. 即左右断相邻, 区间长度为2. 因为我们考虑的是开区间, 区间端点对应的气球是不能被戳爆的, 因此要有这个限制, 否则区间内无气球插入的空间. 而且`val[0]`和`val[n+1]`也是假设出的, 值为`1`但不能被戳的气球
* 当 `i < j - 1`时，我们枚举开区间 (i,j)(i,j) 内的全部位置 \textit{mid}mid，令 \textit{mid}mid 为当前区间第一个添加的气球，该操作能得到的硬币数为 `val[i]×val[mid]×val[j]`。同时我们递归地计算分割出的两区间对 `solve(i,j)` 的贡献，这三项之和的最大值，即为 `solve(i,j)` 的值。这样问题就转化为求 `solve(i,mid)` 和 `solve(mid,j)` ，可以写出方程：

  $$
  \textit{solve}(i,j)= \begin{cases}{} \displaystyle \max\_{\textit{mid} = i + 1}^{j - 1}val\[i] \times \textit{val}\[\textit{mid}] \times \textit{val}\[j] + \textit{solve}(i, \textit{mid}) + \textit{solve}(\textit{mid}, j) ,\&i < j - 1 \ 0, & i \geq j - 1 \end{cases}
  $$

  ​ 为了防止重复计算，我们存储 `solve` 的结果，使用记忆化搜索的方法优化时间复杂度。

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

        @lru_cache(None)
        def coins(left, right):
            if left >= right - 1:  # left在左侧紧邻right就触发终止条件
                return 0

            best = 0
            for i in range(left + 1, right):
                total = val[left] * val[i] * val[right]
                total += coins(left, i) + coins(i, right)
                best = max(best, total)
            return best

        return coins(0, n + 1)
```