The problem
Balloons in a row carry numbers nums[i]. Bursting balloon i earns left × nums[i] × right, where left and right are the numbers on its current neighbours; past either end, count 1. Burst balloons close the gap.
Return the most coins you can collect by bursting them all.
Examples
- Input
nums = [3, 1, 5, 8]
- Output
167
- Input
nums = [1, 5]
- Output
10
Constraints
- 1 ≤ nums.length ≤ 300
- 0 ≤ nums[i] ≤ 100
The idea
Thinking about the first balloon to burst fails: afterwards its neighbours touch, and the two sides are no longer separate problems. Think about the last one instead. If k is the last balloon burst between walls l and r, then while everything else between them is being burst, k stands in the way — the left part and the right part never meet, and k’s own burst then earns v[l] × v[k] × v[r].
So best(l, r) — the most from bursting everything strictly between l and r — is the largest of best(l, k) + v[l] × v[k] × v[r] + best(k, r) over each k between them. Pad the row with a 1 at each end, and fill the table from short ranges to long.
- Time
- O(n³)
- Space
- O(n²)
Solution · every language run against every case
class Solution: def maxCoins(self, nums: List[int]) -> int: v = [1] + nums + [1] # the imaginary 1s at both ends n = len(v) # best[l][r]: the most coins from bursting every balloon strictly between l and r. # Choose k, the LAST of them to burst: at that moment its neighbours are l and r. best = [[0] * n for _ in range(n)] for gap in range(2, n): # shorter ranges first for l in range(0, n - gap): r = l + gap best[l][r] = max(best[l][k] + v[l] * v[k] * v[r] + best[k][r] for k in range(l + 1, r)) return best[0][n - 1]