# 312.戳气球

## 问题描述
[312. 戳气球 (Hard)](https://leetcode.cn/problems/burst-balloons/)

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

现在要求你戳破所有的气球。戳破第 `i` 个气球，你可以获得 `nums[i - 1] * nums[i] *
nums[i + 1]` 枚硬币。 这里的 `i - 1` 和 `i + 1` 代表和 `i`
相邻的两个气球的序号。如果 `i - 1` 或 `i + 1` 超出了数组的边界，那么就当它是一个数字为 `1`
的气球。

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

 **示例 1：**

```
输入：nums = [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
```

**示例 2：**

```
输入：nums = [1,5]
输出：10

```

**提示：**

- `n == nums.length`
- `1 <= n <= 300`
- `0 <= nums[i] <= 100`

## 解题思路
### 分治法+记忆化搜索
首先在数组的首尾各插入元素`1`，以便于计算；

我们可以考虑将这个问题划分成两个不存在相互依赖的子问题，例如考虑`[1, 3, 1, 5, 8, 1]`(注意首尾的`1`是后来单独插入的)，这里我们考虑，假设最后一个戳爆的气球是`5`，那么该问题就可以划分成戳`[1, 3, 1, 5]`和戳`[5, 8, 1]`两组气球的得分再加上最后戳爆气球`5`的得分，（注意这里数组中的第一个和最后一个元素实际上都不是气球的元素，不能戳）。

从递归的角度来说，有`dfs(nums, left, right) = max(dfs(nums, left, mid) + dfs(nums, mid, right) + nums[mid] * nums[l] * nums[r])`；但是这样直接递归必然导致超时，因此我们考虑采用一个数组`cach[left][right]`来保存`dfs(nums, left, right)`的结果，如果`cach[left][right]`不为0，说明`dfs(nums, left, right)`已经计算过了，不需要再重复计算了，直接`return cach[left][right]`就好了。

### 动态规划
由上面的记忆化搜索，其实可以非常方便地改写成动态规划的形式，即
`dp[left][right] = max(dp[left][right], dp[left][mid] + dp[mid][right] + nums[left] * nums[mid] * nums[right])`；

这里状态`dp[left][right]`的定义为：开区间`(left, right)`引爆气球所能获得的最大分数，`mid`表示的是最后一个引爆的气球的坐标；

因此，这里要注意状态转移方程遍历的顺序。

## 代码
### 分治法+记忆化搜索
```cpp
class Solution {
  public:
    保证子问题之间不存在依赖， 分治：递归搜索+保存计算结果
    int dfs(vector<int> &nums, int left, int right, vector<vector<int>> &cach) {
        if (left >= right) {
            return 0;
        }
        int maxnum = 0;
        for (int i = left + 1; i < right; i++) {
            if (cach[left][right] > 0)
                return cach[left][right];
            else
                maxnum = std::max(maxnum, nums[left] * nums[i] * nums[right] + dfs(nums, left, i, cach) + dfs(nums, i, right, cach));
        }
        cach[left][right] = maxnum;
        return maxnum;
    }
    int maxCoins(vector<int> &nums) {
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        int n = nums.size();
        vector<vector<int>> cach(n, vector<int>(n, 0));
        return dfs(nums, 0, n - 1, cach);
    }
}
```

### 动态规划
```cpp
#include <vector>
using std::vector;
class Solution {
  public:
    int maxCoins(vector<int> &nums) {
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for (int l = n - 1; l >= 0; l--) { // 注意这里的遍历顺序！
            for (int r = 0; r < n; r++) {
                for (int mid = l + 1; mid < r; mid++) {
                    dp[l][r] = max(dp[l][r], dp[l][mid] + dp[mid][r] + nums[mid] * nums[l] * nums[r]);
                }
            }
        }
        return dp[0][n - 1];
    }
};
```

## 错误示范
```cpp
class Solution {
  public:
    int dfs(vector<int> &nums, set<int> &rset, set<int, std::greater<int>> &lset, vector<vector<vector<int>>> &cach, int n) {
        if (rset.size() == 2)
            return 0;
        int maxnum = 0; //应该说递归，转化为子问题的时候就出问题了，完全变成回溯了
        for (int i = 1; i <= n; i++) {
            auto iter = rset.find(i);
            if (iter != rset.end()) {
                int idx_left = *lset.upper_bound(i);
                int idx_right = *rset.upper_bound(i);
                if (cach[i][idx_left][idx_right] > 0) {
                    maxnum = std::max(maxnum, cach[i][idx_left][idx_right]);
                } else {
                    rset.erase(i);
                    lset.erase(i);
                    cach[i][idx_left][idx_right] = nums[i] * nums[idx_left] * nums[idx_right] + dfs(nums, rset, lset, cach, n);
                    maxnum = std::max(maxnum, cach[i][idx_left][idx_right]);
                    rset.insert(i);
                    lset.insert(i);
                }
            }
        }
        return maxnum;
    }
    int maxCoins(vector<int> &nums) {
        set<int> rset;
        set<int, std::greater<int>> lset;
        int n = nums.size();
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        for (int i = 0; i < nums.size(); i++) {
            rset.insert(i);
            lset.insert(i);
        }
        vector<vector<vector<int>>> cach(nums.size(), vector<vector<int>>(nums.size(), vector<int>(nums.size(), -1)));
        return dfs(nums, rset, lset, cach, n);
    }
};
```
这份代码，如果去掉保存计算结果的数组，就变成暴力回溯了，那么答案正确，但是会超时，加上保存计算结果的数组之后，答案则会出现错误，`cach[i][left][right] = nums[i] * nums[idx_left] * nums[idx_right] + dfs(nums, rset, lset, cach, n);`从表面含义来看，是在当前气球排列为`left, i, right`的情况下，戳爆`i`所能获得的最大硬币数，问题在于，这样写的到的结果是`[0,1,2], [1,2,3], [2,3,4]...[i - 1, i, rihgt]`中的最大值。