There are n balloons in a row, balloon i showing the number nums[i]. Bursting balloon i earns nums[left] * nums[i] * nums[right] coins, where left and right are its current neighbours; a missing neighbour counts as 1. After a burst, its neighbours become adjacent. Return the maximum coins you can collect by bursting all balloons.
- 1 <= nums.length <= 300
- 0 <= nums[i] <= 100
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Trying every order is O(n!). Picking the first balloon does not split the problem, because the two sides still touch each other later. Picking the last balloon does: if k is burst last in the open range (l, r), everything between l and k and between k and r was already gone, so those two sides are independent, and k earns a[l] * a[k] * a[r]. State: dp[l][r] is the best coins from bursting every balloon strictly between l and r in the padded array a = [1] + nums + [1]. Recurrence: dp[l][r] = max over l < k < r of dp[l][k] + dp[k][r] + a[l]*a[k]*a[r]. Base case: dp[l][l+1] = 0 (nothing in between). Fill by increasing gap r - l.
Algorithm
- Build
a = [1] + nums + [1]and an(n+2) x (n+2)table of zeros. - For gap from 2 to
n + 1, for everylwithr = l + gapinside the array: - Try every
kin(l, r)and keep the bestdp[l][k] + dp[k][r] + a[l]*a[k]*a[r]. - Return
dp[0][n+1].
O(n^3)Space: O(n^2)class Solution: def maxCoins(self, nums: List[int]) -> int: a = [1] + nums + [1] m = len(a) dp = [[0] * m for _ in range(m)] # dp[l][r]: best for balloons strictly between l and r for gap in range(2, m): for l in range(0, m - gap): r = l + gap best = 0 for k in range(l + 1, r): # k is burst last in (l, r) v = dp[l][k] + dp[k][r] + a[l] * a[k] * a[r] if v > best: best = v dp[l][r] = best return dp[0][m - 1]