Implement the burstBalloonsMaxCoins method that returns the maximum coins obtainable by bursting balloons in the best order.
You are given an array where each value represents a balloon. When a balloon at position i is burst, the coins gained are the product of the nearest remaining value on the left, the current value, and the nearest remaining value on the right.
Assume there is a virtual balloon with value 1 outside both ends of the array. Return the maximum coins possible by choosing the best bursting order.
Example 1
[3,1,5,8]4167Example 2
[1,5]210Example 3
[7]17The difficult part is that bursting one balloon changes its neighbors. Instead of thinking about the first balloon to burst, think about the last balloon burst inside an interval.
If a balloon is the last one burst between two boundaries, its left and right neighbors are fixed. Use interval dynamic programming where dp[left][right] stores the maximum coins from bursting balloons strictly between left and right.
Try every balloon as the last balloon in each interval and keep the best result.
Pseudocode:
function burstBalloonsMaxCoins(nums, size):
values = [1] + nums + [1]
create dp table filled with 0
for length from 2 to size + 1:
for left from 0 to size + 1 - length:
right = left + length
for last from left + 1 to right - 1:
coins = values[left] * values[last] * values[right]
coins += dp[left][last] + dp[last][right]
dp[left][right] = max(dp[left][right], coins)
return dp[0][size + 1]