Pop Balloons For Coins
Problem
A row of balloons each carries a number. Popping a balloon pays its number multiplied by the numbers of the balloons currently to its left and right; a missing neighbour counts as 1. The row closes up after every pop, so the neighbours change as you go. Pop every balloon and return the largest total payment possible.
Examples
Input: values = [3, 1, 5, 8]
Output: 167
Why: popping in the order 1, 5, 3, 8 pays 15 + 120 + 24 + 8Input: values = [1, 5]
Output: 10
Why: popping the 1 first pays 5, and the lone 5 then pays another 5Input: values = []
Output: 0
Why: edge case, there is nothing to popHints
0 / 3
Deciding which balloon to pop first is a trap, because that choice tears the row into two pieces whose neighbours then depend on each other.
Ask instead which balloon inside a stretch is popped last. That balloon's neighbours at the moment it pops are exactly the two walls of the stretch, which never move.
Pad the row with a balloon of value one at each end so the walls always exist. For every stretch between two walls, try each inner balloon as the last one popped: its payment is wall times balloon times wall, plus the best totals for the two stretches it splits the rest into. Fill stretches from the narrowest upward.
Solution
Choosing the first pop is unusable because it makes the two halves interact, while choosing the last pop inside a stretch fixes that balloon's neighbours to be the stretch's own walls, which never change. That turns the problem into intervals: for each pair of walls, the best total is the maximum over inner balloons of the two sub-stretch totals plus the payment of that final pop. Padding both ends with a value of one removes the missing-neighbour special case. Filling by increasing width guarantees sub-stretches are ready when needed. Time is O(n cubed) and space is O(n squared).
def max_coins(values):
pad = [1] + values + [1] # imaginary balloons of value one at both ends
n = len(pad)
best = [[0] * n for _ in range(n)]
for width in range(2, n): # the distance between the two walls
for left in range(n - width):
right = left + width
for last in range(left + 1, right): # the balloon popped last in here
gain = pad[left] * pad[last] * pad[right]
best[left][right] = max(best[left][right],
best[left][last] + gain + best[last][right])
return best[0][n - 1]
print(max_coins([3, 1, 5, 8])) # -> 167
print(max_coins([1, 5])) # -> 10
print(max_coins([])) # -> 0Stuck on the idea rather than the code? Interval DP covers it.