806. Burst Balloons (Interval DP via Recursion)

Given array nums of balloon values, burst all to maximize coins. Bursting balloon i earns nums[left]*nums[i]*nums[right] where left/right are adjacent surviving balloons (boundaries = 1). Return max coins.

Input: An integer array.

Output: Integer.

Examples

Input: [3,1,5,8]
Output: 167
Explanation: Burst order 1,5,3,8 yields 3*1*5+3*5*8+1*3*8+1*8*1=167.

Input: [1,5]
Output: 10
Explanation: Burst 1 then 5: 1*1*5+1*5*1=10.

Constraints

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

Asked by