Pattern visualizer
Burst Balloons
Asking which balloon to burst FIRST goes nowhere: it splits the row into two halves that are no longer independent, because the balloons either side of the gap become neighbours. Asking which one bursts LAST fixes that. If k is last inside the open range (l, r), then everything left of k is gone before k pops and everything right of k is gone too, so the two halves never interact — and when k finally bursts, its neighbours are exactly l and r, which are still standing. That makes the score l*k*r independent of how the halves were played, so dp[l][r] = max over k of dp[l][k] + dp[k][r] + A[l]*A[k]*A[r]. Padding both ends with a 1 removes the edge cases. Animated on: nums=[3,1,5,8] — burst every balloon; bursting i pays nums[left]*nums[i]*nums[right] with the CURRENT neighbours. Maximise the total..
Interval DP on the LAST balloon burst, not the first
dp[l][r] — most coins obtainable from the balloons strictly between padded positions l and r
Pad the row with a 1 at each end so every real balloon has a neighbour: [1, 3, 1, 5, 8, 1]. dp[l][r] means "best coins from bursting only what lies BETWEEN l and r". The 0s are ranges with nothing inside them.
1FUNCTION maxCoins(nums)2 A <- [1] + nums + [1]3 n <- LENGTH(A)4 dp <- n x n table of 05 FOR gap FROM 2 TO n-16 FOR l FROM 0 TO n-1-gap7 r <- l + gap8 FOR k FROM l+1 TO r-19 dp[l][r] <- MAX(dp[l][r], dp[l][k] + dp[k][r] + A[l] * A[k] * A[r])10 RETURN dp[0][n-1]
← / → step · space play · Home restart