> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/fidai-biao-yiinput-i-wei-jie-wei-de-zhi/burst-balloons.md).

# Burst Balloons

> Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums\[left] \* nums\[i] \* nums\[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.
>
> Find the maximum coins you can collect by bursting the balloons wisely.
>
> Note:
>
> (1) You may imagine nums\[-1] = nums\[n] = 1. They are not real therefore you can not burst them.
>
> (2) 0 ≤ n ≤ 500, 0 ≤ nums\[i] ≤ 100
>
> Example:
>
> Given \[3, 1, 5, 8]
>
> Return 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

## Thoughts

给定一个数组，元素值代表收益，每次选择一个元素去掉，得到的收益为它当前的左边元素*它*它右边元素。action为选择一个元素k去掉，相当于根据k做划分。如果正着想很难理清状态，但倒着可以知道最后一次只会爆掉一个元素k，因此让dp\[j]\[i]表示爆j和i之间的(不包括i和j)所有气球能获得的最大收益，让k表示j和i之间中最后一个爆掉的气球, 那么爆k时的收益为coins\[j] *coins\[k]* coins\[i] + dp\[j]\[k] + dp\[k]\[i]。 让k在\[j + 1, i - 1]依次遍历即可。

## Code

```cpp
/*
 * @lc app=leetcode id=312 lang=cpp
 *
 * [312] Burst Balloons
 */
class Solution {
public:
    int maxCoins(vector<int>& nums) {
        const int N = nums.size();
        vector<int> coins(N + 2);
        coins[0] = coins[N + 1] = 1;
        for (int i = 0; i < N; ++i) {
            coins[i + 1] = nums[i];
        }
        vector<vector<int>> dp(N + 2, vector<int>(N + 2));
        for (int i = N - 1; i >= 0; --i) {
            for (int j = i + 2; j <= N + 1; ++j) {
                for (int k = i + 1; k <= j - 1; ++k) {
                    dp[i][j] = max(dp[i][j], coins[i] * coins[k] * coins[j] + dp[i][k] + dp[k][j]);
                }
            }
        }
        return dp[0][N + 1];
    }
};


```

```java
class Solution {
    public int maxCoins(int[] nums) {
        int[] coins = new int[nums.length + 2];
        int n = 1; 
        for (int num : nums) {
            if (num != 0) {
                coins[n++] = num;
            }
        }

        coins[0] = coins[n++] = 1;
        int[][] f = new int[n][n];
        for (int i = 2; i < n; i++) {
            for (int j = i - 2; j >= 0; j--) {
                for (int k = j + 1; k <= i - 1; k++) {
                    f[j][i] = Math.max(f[j][i],
                                             coins[j] * coins[k] * coins[i] + f[j][k] + f[k][i]);
                }
            }
        }

        return f[0][n - 1];
    }
}
```

## Analysis

Errors:

1. j从小到大遍历

时间复杂度O(N^3), 空间O(N^2).