Burst Balloons

You are given n balloons, indexed from 0 to n - 1, each painted with a number represented by an array nums. You need to burst all the balloons to maximize the coins you collect. Bursting the i-th balloon gives coins equal to nums[i - 1] * nums[i] * nums[i + 1]. If i - 1 or i + 1 goes out of bounds, treat it as a balloon with a 1 on it. Return the maximum coins you can collect by bursting the balloons wisely.

Constraints

• n == nums.length
• 1 <= n <= 300
• 0 <= nums[i] <= 100