> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/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:**

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

```java
class Solution {
    public int maxCoins(int[] nums) {
        int[][] dp = new int[nums.length][nums.length];
        return maxCoins(nums, 0, nums.length - 1, dp);
    }

    public int maxCoins(int[] nums, int start, int end, int[][] dp) {
        if (start > end)
            return 0;
        // If we already have answer for this subarray
        if (dp[start][end] != 0)
            return dp[start][end];

        int max = 0;
        for (int i = start; i <= end; i++) {
            // Try bursting all balloons one by one for first burst
            int val = maxCoins(nums, start, i - 1, dp) + get(nums, i) * get(nums, start - 1) * get(nums, end + 1)
                    + maxCoins(nums, i + 1, end, dp);
            max = Math.max(max, val);
        }
        dp[start][end] = max;
        return max;
    }

    public int get(int[] nums, int i) {
        if (i == -1 || i == nums.length)
            return 1;
        return nums[i];
    }
}
```