# Question

Formatted question description: https://leetcode.ca/all/312.html

 312	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]   -->    --> []
coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

@tag-dp


# Algorithm

Maintain a two-dimensional dynamic array dp, where dp[i][j] represents the most gold coins that can be obtained by bursting all balloons in the interval [i,j].

dp[i][j] = max(dp[i][j], nums[i-1] * nums[k] * nums[j + 1] + dp[i][k-1] + dp[ k + 1][j]) (i ≤ k ≤ j )

Example [3, 1, 5, 8], the general traversal order is:

 -> [3, 1] -> [3, 1, 5] -> [3, 1, 5, 8] ->  -> [1, 5] -> [1, 5, 8 ] ->  -> [5, 8] -> 


Obviously it is not the traversal order we need. The correct order should be to first traverse all the intervals of length 1, then the intervals of length 2, and then accumulate the lengths in turn, until the entire interval is traversed:

 ->  ->  ->  -> [3, 1] -> [1, 5] -> [5, 8] -> [3, 1, 5] -> [1, 5, 8] -> [3, 1, 5, 8]


In fact, only the upper right triangle area of the dp array is updated here, and the final value to be returned is stored in dp[n], where n is the number of array nums before adding 1 at both ends.

Java