Burst balloons
A row of balloons has a number on each one, given as the list nums. You burst the balloons one at a time, in any order you choose, until none is left.
Bursting a balloon earns coins: its number times the numbers on its two nearest balloons still in the row, one on the left and one on the right. When no balloon is left on a side, use 1 for that side. Return the largest total of coins you can earn.
nums = [2, 4, 3]Output33Burst the 4 first: 2 × 4 × 3 = 24. Now the 2 and the 3 are neighbors. Burst the 2: 1 × 2 × 3 = 6. Burst the 3: 1 × 3 × 1 = 3. Total 24 + 6 + 3 = 33.
nums = [1, 5]Output10Burst the 1 first: 1 × 1 × 5 = 5, then the 5 alone: 1 × 5 × 1 = 5. Bursting the 5 first earns only 5 + 1 = 6.
nums = [9, 1, 1, 9]Output180Burst the two 1s first, while the 9s are their neighbors: 9 × 1 × 1 = 9 and 9 × 1 × 9 = 81. Then 1 × 9 × 9 = 81 and 1 × 9 × 1 = 9. Total 9 + 81 + 81 + 9 = 180.
1 ≤ len(nums) ≤ 300
0 ≤ nums[i] ≤ 100
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.