233. Burst Balloons

Hard · Dynamic Programming

You have `n` balloons indexed 0 to n-1. Each balloon has a number. If you burst balloon `i`, you earn `nums[i-1] * nums[i] * nums[i+1]` coins. Balloons at the edges treat missing neighbours as 1. Return the maximum coins you can collect by bursting all balloons.

Examples

Example 1
Input: nums = [3, 1, 5, 8]
Output: 167
Explanation: Burst 1: 3×1×5=15, burst 5: 3×5×8=120, burst 3: 1×3×8=24, burst 8: 1×8×1=8 → 167

Constraints