2-D Dynamic Programming Splitting a range
572. Burst Balloons
There are n balloons in a row, and balloon i has the number nums[i] on it. You burst the balloons one
at a time, in any order you choose, until none are left.
Bursting a balloon gives you coins: its number times the numbers of its two neighbours. A neighbour is the nearest balloon on that side that has not burst yet. When a balloon bursts, the balloons on either side of it become neighbours. If a balloon has no neighbour on one side, that side counts as 1.
Return the most coins you can collect.
Example 1
Input: nums = [4, 2, 3, 5]
109Explanation: Burst 2 for 4 × 2 × 3 = 24 coins, then 3 for 4 × 3 × 5 = 60, then 4 for 1 × 4 × 5 = 20, and
last 5 for 1 × 5 × 1 = 5. That is 109 coins.
Example 2
Input: nums = [7]
7Explanation: The only balloon has no neighbours, so both sides count as 1, and it gives 1 × 7 × 1 = 7.
Example 3
Input: nums = [10000, 10000, 10000]
1000100010000Explanation: Burst the middle balloon first, for 10000 × 10000 × 10000 coins. Then one end balloon gives 10000 × 10000, and the last one gives 10000.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 3000 ≤ nums[i] ≤ 104
Clarifying questions
What you would ask an interviewer before writing any code.