Dynamic ProgrammingInterval DP
There are n balloons, each painted with a number. Bursting balloon i gives you nums[left] * nums[i] * nums[right] coins, where left and right are the nearest balloons still unburst on each side (a missing balloon counts as 1). Find the maximum coins you can collect by bursting all the balloons in the best order.
Input
Line 1: n. Line 2: the n balloon numbers.
Output
Print the maximum number of coins.
Constraints
1 <= n <= 50 0 <= each number <= 100
Example 1
Input
4 3 1 5 8
Output
167
Burst 1, then 5, then 3, then 8 for 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167.