#25HardDynamic Programming & Divide and Conquer· Interval DP on the Last Choice

Burst Balloons

A row of `n` balloons is numbered `0` to `n - 1`, and balloon `i` carries the number `nums[i]`. You burst the balloons one at a time, in any order, until none are left. Bursting a balloon earns `left * value * right` coins, where `value` is its own number and `left` and `right` are the numbers on its **current** neighbours, i.e. the nearest balloons on each side that have not been burst yet. If there is no balloon on one side, that side counts as `1`. Return the maximum total number of coins you can earn.

Input format

nums: array of non-negative integers

Output format

Integer: the maximum number of coins

Examples

Input: nums = [3, 1, 5, 8]

Output: 167

One optimal order bursts 1, 5, 3, 8: 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 15 + 120 + 24 + 8 = 167.

Input: nums = [1, 5]

Output: 10

Burst 1 first (1*1*5 = 5), then 5 (1*5*1 = 5), for 10 in total.

Input: nums = [0, 3]

Output: 3

A balloon with 0 earns nothing and makes any neighbour product 0, so it should go first: 0 + 3 = 3.

Constraints

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

Study first

Dynamic Programming Patterns

#dynamic-programming
#interval-dp
#divide-and-conquer
#arrays