Dynamic Programming
LC #312Hard
Burst Balloons
Dynamic Programming
AmazonGoogleProblem
Burst balloons to maximize coins. Bursting balloon i gives nums[i-1]*nums[i]*nums[i+1] coins.
dynamic-programminginterval-dp
Constraints
- ›1 ≤ n ≤ 300
- ›0 ≤ nums[i] ≤ 100
- ›Padding: nums[-1] = nums[n] = 1 (virtual balloons)
Example
Input
nums = [3, 1, 5, 8]Output
167Why
Burst order: 1,5,3,8 → 3×1×5 + 3×5×8 + 1×3×8 + 1×8×1 = 15+120+24+8=167