Given n balloons, each with a number on it, you may burst the balloons in any order. When you burst balloon i, you gain coins equal to nums[left] * nums[i] * nums[right]. Return the maximum coins you can collect. This is a classic optimal-substructure interval DP problem.
nums = balloon values
maximum coins obtainable
Example 1:
Input:
nums = [3,1,5,8]
Output:
167
Explanation:
This is the classic example from the problem statement.
Example 2:
Input:
nums = [1,5]
Output:
10
Explanation:
Bursting both balloons yields 10 coins.