Description
Burst every balloon in a row to maximize coins. Bursting index i earns its value times its two currently adjacent values; a missing outside neighbor has value 1. Values are nonnegative.
Solution
def max_coins(nums):
values = [1] + nums + [1]
size = len(values)
dp = [[0] * size for _ in range(size)]
for width in range(2, size):
for left in range(size - width):
right = left + width
dp[left][right] = max(
dp[left][last] + values[left] * values[last] * values[right] + dp[last][right]
for last in range(left + 1, right)
)
return dp[0][-1]Examples
Example 1
- Input
[[3,1,5,8]]- Output
167
An optimal order is 1, 5, 3, 8.
Example 2
- Input
[[1,5]]- Output
10
Burst 1 first, earning 5, then 5, earning 5.
Example 3
- Input
[[0]]- Output
0
A zero balloon contributes no coins.
Approach
Pad the values with 1 on each end. For every open interval, try each interior balloon as the last to burst. Its neighbors are then the interval boundaries, and left and right subproblems become independent.
Time & space
O(n^3) time and O(n^2) auxiliary space, where n is balloon count.