Burst Balloons (Interval DP)

You are given an array nums of balloon values. When you burst balloon i, you gain nums[left] * nums[i] * nums[right], where left and right are the nearest unburst balloons. Treat missing neighbors as 1.

Return the maximum coins you can collect.

Function signature

func BurstBalloons(nums []int) int

Example

nums = [3,1,5,8]
output = 167

Constraints

• 0 <= len(nums) <= 300
• 0 <= nums[i] <= 100

Notes

• Interval DP with O(n^3) time.