Burst Balloons
Hard · 2-D Dynamic Programming
You are given a row of balloons, each marked with a number of coins. You may pop the balloons one at a time; popping a balloon rewards you with coins equal to the product of the numbers on the balloon just to its left, the balloon itself, and the balloon just to its right (treating a missing neighbor, because it was already popped or is off the edge, as having value 1). Choose the order of popping that maximizes the total coins collected, and return that maximum total. Every balloon must eventually be popped.
Examples
Input: nums = [3,1,5,8]
Output: 167
Why: Popping in order 1,5,3,8 gives 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 15+120+24+8 = 167, which is the best possible.Input: nums = [1,5]
Output: 10
Why: Popping 1 first gives 1*1*5=5, then popping 5 gives 1*5*1=5, total 10, which beats the other order (1+5=6).Input: nums = [7]
Output: 7
Why: The single balloon is popped with both neighbors missing, giving 1*7*1=7.Constraints
1 <= nums.length <= 300, 0 <= nums[i] <= 100
Practise it by voice
Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.
This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Burst Balloons. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.