# 312.戳气球

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

## 一：回溯

超时

```python
class Solution:
    def maxCoins(self, nums) -> int:
        self.res = 0
        def bt(nums, score):
            n = len(nums)
            if n ==0:
                self.res = max(self.res ,score)
                return
            for i in range(n):
                tmp = nums
                s=0
                if n==1:
                    s = nums[0]
                elif i == 0:
                    s = nums[i] *nums[i+1]
                elif i == n-1:
                    s = nums[i-1]*nums[i]
                else:
                    s = nums[i-1]*nums[i]*nums[i+1]
                nums = nums[0:i] + nums[i + 1:]
                bt(nums, score+s)
                nums = tmp
        bt(nums, 0)
        return self.res
```

## 二：dp

逆向思维，考虑气球i和气球j之间最后一个被戳破的气球k是哪个，就是一种选择 用`dp[i][j]`表示戳破气球i和j之间的最高分，开区间不包含i和j，易知j <= i+1时dp=0

![](https://3747312504-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LXItOiQMDgh0S65YZXd%2Fuploads%2Fgit-blob-b3847167956610e315733c85d580bd2959227e46%2F312_1.webp?alt=media)

由于是开区间，`dp[i][k]`和`dp[k][j]`都不会影响气球k（i\<k\<j)，最后戳破气球k前这两部分都已戳破，k相邻的是i和j，此时戳破k，得分即状态转移方程：

```
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + s[i] * s[k] * s[j])
                          戳(i,k)     戳(k,j) 	     戳k
```

在原数组首尾添加辅助元素1，数组长度变为n+1，最后所求为`dp[0][n+1]`

![](https://3747312504-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LXItOiQMDgh0S65YZXd%2Fuploads%2Fgit-blob-0fc7de049ea7b9fd040b8c5e9d41c89c962f782f%2F312_2.jpg?alt=media)

由上图可知对角线上方的斜线也是0，因此i遍历可以从倒数第三行开始，即n-1

```python
class Solution:
    def maxCoins(self, nums) -> int:
        n = len(nums)
        s = nums.copy()  # 辅助数组
        s = [1] + s + [1]

        dp = [[0] * (n + 2) for _ in range(n + 2)]
        for i in range(n - 1, -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] + s[i] * s[k] * s[j])

        return dp[0][n + 1]
```


---

# 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://cai-sen-se.gitbook.io/leetcode/201-400/312.-chuo-qi-qiu.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.