0%

### 题目描述

You are given `n` balloons, indexed from `0` to `n - 1`. Each balloon is painted with a number on it represented by an array `nums`. You are asked to burst all the balloons.

If you burst the `ith` balloon, you will get `nums[i - 1] * nums[i] * nums[i + 1]` coins. If `i - 1` or `i + 1` goes out of bounds of the array, then treat it as if there is a balloon with a `1` painted on it.

Return the maximum coins you can collect by bursting the balloons wisely.

### 例子

#### 例子 1

Input: `nums = [3,1,5,8]`
Output: `167`
Explanation:
`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

Input: `nums = [1,5]`
Output: `10`

### Constraints

• `n == nums.length`
• `1 <= n <= 500`
• `0 <= nums[i] <= 100`

### 解题思路

• 遍历区间长度 `len`，从 `1``n`
• 给定区间长度的情况下，遍历区间左端点 `left`，从 `1``n - len + 1`
• 此时用于区间长度和左端点固定，因此右端点也是固定的：`right = left + len - 1`
• 此外还需要遍历区间中剩下的气球 `middle``left``right`
• 气球爆炸顺序为： `left to middle - 1` - `middle + 1 to right` (这两个顺序先后无所谓，爆破完后剩余中间的气球 `middle`，以及区间外的两个气球)
• 状态更新方程为：

• 时间复杂度: O(n^3)
• 空间复杂度: O(n^2)

GitHub 代码同步地址： 312.BurstBalloons.cpp

GitHub: Leetcode-C++-Solution