# 312     Burst Balloons

## 312. [Burst Balloons](https://leetcode.com/problems/burst-balloons/description/)

## 1. Question

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

## 2. Implementation

**(1) DP**

```java
class Solution {
    public int maxCoins(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int n = nums.length;
         // Add 2 because we wanna include the boundary nums[-1] and nums[n]
        int[] coins = new int[n + 2];
        coins[0] = 1;
        coins[n + 1] = 1;

        for (int i = 1; i <= n; i++) {
            coins[i] = nums[i - 1];
        }

        // 我们要找的答案在dp[1][n]
        // dp[i][j] means the max coins we can collect in the coin(i..j)
        int[][] dp = new int[n + 2][n + 2];

        for (int len = 1; len <= n; len++) {
            for (int start = 1; start <= n - len + 1; start++) {
                int end = start + len - 1;

                for (int mid = start; mid <= end; mid++) {
                    dp[start][end] = Math.max(dp[start][end], dp[start][mid - 1] + dp[mid + 1][end] + coins[start - 1] * coins[mid] * coins[end + 1]);
                }
            }
        }
        return dp[1][n];
    }
}
```

## 3. Time & Space Complexity

**DP:** 时间复杂度O(n^3), 空间复杂度O(n^2)
