Burst Balloons
Problem
A row of balloons each has a number. Bursting a balloon earns the product of its number and the numbers of its current left and right neighbours (treat missing neighbours as 1), and then it disappears. Return the maximum total you can earn by bursting all of them.
Examples
Constraints
- • 1 <= nums.length <= 300
- • 0 <= nums[i] <= 100
Hints & approach
Hint 1
Choosing the first balloon to burst leaves neighbours that keep changing — hard to model.
Hint 2
Instead, pick the balloon that is burst LAST inside an interval; its neighbours are then the fixed interval boundaries.
Hint 3
Pad the array with 1s and let dp[l][r] be the best score for bursting everything strictly between l and r.
Approachtry the hints first
Pad nums with a 1 on each end. Let dp[l][r] be the best coins from bursting all balloons strictly between indices l and r. If k is the last one burst in that range, it earns a[l]·a[k]·a[r] and the two sides are independent: dp[l][r] = max over k of dp[l][k] + dp[k][r] + a[l]·a[k]·a[r]. Empty intervals score 0. Fill by increasing interval length; the answer is dp[0][n+1].
Time O(n³) · Space O(n²)