# 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:**

* You may imagine `nums[-1] = nums[n] = 1`. They are not real therefore you can not burst them.
* 0 ≤ `n` ≤ 500, 0 ≤ `nums[i]` ≤ 100

Example:

```
Input: [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
```

## Analysis

A very nice analysis on LeetCode talking about several approaches from brute-force to divide and conquer as well as dynamic programming:

<https://leetcode.com/problems/burst-balloons/discuss/76228/Share-some-analysis-and-explanations>

一、利用分治法Divide and Conquer结合记忆化memoization

二、或者利用区间型动态规划Dynamic Programming

### **Divide and Conquer with Memoization**

<https://mnmunknown.gitbooks.io/algorithm-notes/625,_dong_tai_gui_hua_ff0c_qu_jian_lei_dp.html>

<https://leetcode.com/problems/burst-balloons/discuss/76245/Easiest-Java-Solution>

> subproblems are overlapped, so we can use divide and conquer + cache
>
> * Balloons `0, 1, ..., n - 1`
> * What is the max value if we burst all of them`[0, n - 1]`?
> * Let's first consider bursting`[start, end]` (including `start` and `end` boundaries)
> * Imagine index `i` as the last one in the interval to be bursted
> * `[start, ... i - 1, (i), i + 1 ... end]`
> * Before the end, we already bursted `[start, i - 1]` and `[i + 1, end]`
> * Before the end, boundaries `start - 1` , `i` , `end + 1` are always there
> * This helps us calculate coins without worrying about details inside`[start, i - 1]` and `[i + 1, end]`
> * So the range can be divided into `start - 1` ,`maxCoin(start, i - 1)`, `i`, `maxCoins(i + 1, end)`, `end + 1`

基本思想就是在区间`[start, end]`中循环`i`，`i`作为该区间内最后被爆的气球，这样区间被分成了左右两个区间，再依次递归地寻找 `[start, i - 1]` 和 `[i + 1, end]` 的区间。这样就变成了子问题，而子问题区间上是可能有重叠的，因此可以用memoization来优化递归。

### **Dynamic Programming**

这题的难点在于，如何在动态变化的数组中，正确定义并计算subproblem.

因为数组一直在变化，如何计算每次打爆获得的coin呢？

是否可以将子问题定义为寻找(left, right)区间内能得到最多的coin数目？\
难想到的是从最后被打爆的气球入手，这种情况下，区间的左右两个两个元素就是确定的，而改变（循环`i`）区间内最后被打爆的气球则会得到不同的结果，从而找到最大

**State:**

* `dp[i][j]`表示 i 到 j 区间中，打爆所有气球的最大coin数目

**Function:**

* 对于所有k属于`{i,j}`, 表示第k号气球最后打爆。`k` **is the last balloon to burst.**
  * `midValue = arr[i- 1] * arr[k] * arr[j + 1];`
  * `dp[i][j] = max(dp[i][k-1] + d[k+1][j] + midvalue)`

**Initialize:**

* for each `i`
  * `dp[i][i] = 0`

**Answer:**

* `dp[0][n-1]`

## Solution

**Divide & Conquer + Recursive + Memoization - Easy to Understand Solution (**&#x31;6 ms, faster than 14.04%)

<https://leetcode.com/problems/burst-balloons/discuss/76245/Easiest-Java-Solution>

`start`, `end` boundary included (boundaries will be burst)

`[start, ... i - 1, (i), i + 1 ... end]`

```java
class Solution {
    public int maxCoins(int[] nums) {
        int[][] dp = new int[nums.length][nums.length];
        return maxCoinsHelper(nums, 0, nums.length - 1, dp);
    }
    public int maxCoinsHelper(int[] nums, int start, int end, int[][] dp) {
        if (start > end) return 0;
        if (dp[start][end] != 0) return dp[start][end];
        int max = 0;
        for (int i = start; i <= end; i++) {
            int val = maxCoinsHelper(nums, start, i - 1, dp) + 
                maxCoinsHelper(nums, i + 1, end, dp) + 
                getVal(nums, start - 1) * getVal(nums, i) * getVal(nums, end + 1);
            max = Math.max(max, val);
        }
        dp[start][end] = max;
        return max;
    }
    private int getVal(int[] nums, int i) {
        if (i == -1 || i == nums.length) {
            return 1;
        }
        return nums[i];
    }
}
```

**\*(Favorite)** - **Same idea as above (Divide & Conquer with Memoization) but faster performance (**&#x36;ms 87.86%**)**

Building a new array first for faster access, compared to above `getVal()` function

```java
public class Solution {
    public int maxCoins(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int n = nums.length;
        int[] arr = new int[n + 2];
        arr[0] = 1;
        arr[n + 1] = 1;
        for(int i = 0; i < n; i++){
            arr[i + 1] = nums[i];
        }

        int[][] dp = new int[n + 2][n + 2];


        return memoizedSearch(1, n, arr, dp);
    }

    private int memoizedSearch(int start, int end, int[] arr, int[][] dp){
        if(dp[start][end] != 0) return dp[start][end];

        int max = 0;
        for(int i = start; i <= end; i++){
            int cur = arr[start - 1] * arr[i] * arr[end + 1];
            int left = memoizedSearch(start, i - 1, arr, dp);
            int right = memoizedSearch(i + 1, end, arr, dp);

            max = Math.max(max, cur + left + right);
        }

        dp[start][end] = max;

        return max;
    }
}
```

**Other answers for reference**&#x20;

**\*Divide and Conquer, Memoization, Recursive - (Runtime: 5 ms, faster than 99.18%)**

(not including boundaries in the recursion - boundary balloons not bursted)

```java
class Solution {
    public int maxCoins(int[] iNums) {
        int[] nums = new int[iNums.length + 2];
        int n = 1;
        for (int x : iNums) if (x > 0) nums[n++] = x;
        nums[0] = nums[n++] = 1;


        int[][] memo = new int[n][n];
        return burst(memo, nums, 0, n - 1);
    }

    public int burst(int[][] memo, int[] nums, int left, int right) {
        if (left + 1 == right) return 0;
        if (memo[left][right] > 0) return memo[left][right];
        int ans = 0;
        for (int i = left + 1; i < right; ++i)
            ans = Math.max(ans, nums[left] * nums[i] * nums[right] 
                           + burst(memo, nums, left, i) + burst(memo, nums, i, right));
        memo[left][right] = ans;
        return ans;
    }
}
```

**Dynamic Programming** - 6 ms , faster than 88.28%

```java
public int maxCoins(int[] iNums) {
    int[] nums = new int[iNums.length + 2];
    int n = 1;
    for (int x : iNums) if (x > 0) nums[n++] = x;
    nums[0] = nums[n++] = 1;


    int[][] dp = new int[n][n];
    for (int k = 2; k < n; ++k)
        for (int left = 0; left < n - k; ++left) {
            int right = left + k;
            for (int i = left + 1; i < right; ++i)
                dp[left][right] = Math.max(dp[left][right], 
                nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right]);
        }

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

## Reference

* \[区间类DP总结]\([https://www.jianshu.com/p/4c462077f8f2\\](https://www.jianshu.com/p/4c462077f8f2%29\\)


---

# 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://aaronice.gitbook.io/lintcode/dynamic_programming/burst-balloons.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.