Interval DP (last operation)

39 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

You have balloons in a row, [3, 1, 5, 8]. Bursting a balloon earns you the product of it and its two current neighbours, and the row closes up afterwards. Outside the row imagine invisible balloons worth 1 on each side. Which order earns the most coins?

By hand you would try orders. Burst 1 first: 3 × 1 × 5 = 15, leaving [3, 5, 8]. Then 5: 3 × 5 × 8 = 120, leaving [3, 8]. Then 3: 1 × 3 × 8 = 24, then 8: 1 × 8 × 1 = 8. Total 167. Is that the best? There are 4 × 3 × 2 × 1 = 24 orders for four balloons; for 12 balloons there are 479 million. Trying orders is hopeless, and the obvious shortcut fails: after bursting the first balloon, its neighbours become adjacent, so the two halves of the row are no longer separate problems.

Build the structure, one piece at a time

The trick is to think about the last balloon burst instead of the first. Add the invisible 1s so the row is [1, 3, 1, 5, 8, 1] with indices 0 to 5. Consider an open interval (i, j): the balloons strictly between positions i and j, where the balloons at i and j are still standing. If balloon k is the last one burst inside that interval, then at that moment its neighbours are exactly i and j, so it earns v[i] × v[k] × v[j]. Everything left of k was burst while i and k stood, everything right of k while k and j stood. The two sides never touch, so they are independent smaller problems.

So the structure is a table dp[i][j] = most coins from bursting everything strictly between i and j. Fill it by the width of the interval, narrow first.

1. Width 2, nothing inside: dp[i][i+1] = 0 for every i.
2. Width 3, one balloon inside: dp[0][2] = 1 × 3 × 1 = 3, dp[1][3] = 3 × 1 × 5 = 15, dp[2][4] = 1 × 5 × 8 = 40, dp[3][5] = 5 × 8 × 1 = 40.
3. Width 4, two balloons inside, two choices of last: dp[1][4] = max(last is 1: 3 × 1 × 8 + 0 + 40 = 64, last is 5: 3 × 5 × 8 + 15 + 0 = 135) = 135.
4. Width 6, the whole row: last is 8 gives 1 × 8 × 1 + dp[0][4] + 0 = 8 + 159 = 167; the other choices score less. Answer 167.

Each cell only needs cells of smaller width, which are already final because of the fill order.

Why it is correct

The invariant is that dp[i][j] is the true optimum for the balloons strictly inside (i, j) with i and j standing. Every order of bursting the inside has some last balloon k, so the optimum equals the best over k of: coins for k last, plus the best for the left part, plus the best for the right part. The left and right parts are smaller intervals with their own boundaries standing, so by the invariant their table cells are their true optima. Taking the maximum over all k therefore gives the true optimum for (i, j).

dp[i][j] = max over i < k < j of ( v[i]·v[k]·v[j] + dp[i][k] + dp[k][j] )

Why it is fast

With n balloons plus two borders there are about n²/2 intervals, and each interval tries at most n choices of k. That is O(n³) multiplications and additions: for 12 balloons roughly 1,000 steps instead of 479 million orders, and for 300 balloons about 27 million steps, still instant. Memory is the n × n table.

How to recognise it in an interview

Cues: items in a row, an operation that removes or merges neighbours, and a cost that depends on what is adjacent at that moment. The greedy and left-to-right ideas fail because removing one item changes its neighbours. Say: I will define the answer for every interval and decide which element is handled last, so the two sides become independent. Burst Balloons is the textbook case. Minimum Cost to Merge Stones and Strange Printer use the same interval table with a different combine rule, and Predict the Winner fills intervals from the ends inward.

02The idea in one line

Choose the last element burst/removed in [i, j]; the sides become independent.

Reach for it when: Burst balloons, minimum cost to merge stones, strange printer, remove boxes, matrix chain.

Cost: O(n³) time.

03The walk-through, step by step

The video works one example: Burst Balloons on [3,1,5,8]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Pick the balloon burst last in (i, j): its neighbours are then i and j, so the two sides are independent
2. dp[0][2] = 3: burst 3 last, 1·3·1 + dp[0][1] + dp[1][2]
3. dp[1][3] = 15: burst 1 last, 3·1·5 + dp[1][2] + dp[2][3]
4. dp[2][4] = 40: burst 5 last, 1·5·8 + dp[2][3] + dp[3][4]
5. dp[3][5] = 40: burst 8 last, 5·8·1 + dp[3][4] + dp[4][5]
6. dp[0][3] = 30: burst 3 last, 1·3·5 + dp[0][1] + dp[1][3]
7. dp[1][4] = 135: burst 5 last, 3·5·8 + dp[1][3] + dp[3][4]
8. dp[2][5] = 48: burst 8 last, 1·8·1 + dp[2][4] + dp[4][5]
9. dp[0][4] = 159: burst 3 last, 1·3·8 + dp[0][1] + dp[1][4]
10. dp[1][5] = 159: burst 8 last, 3·8·1 + dp[1][4] + dp[4][5]
11. dp[0][5] = 167: burst 8 last, 1·8·1 + dp[0][4] + dp[4][5]
12. dp[0][5] = 167: the whole array, every length filled from short to long
13. n² intervals × n split points: O(n³)

04Asked at Google

9 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Dynamic Programming: 1-D linear DP, Kadane (best ending here), Longest increasing subsequence, Grid path DP, 0/1 knapsack (subset sum), Unbounded knapsack (coin change), Two-sequence DP (LCS / edit distance), Wildcard / regex matching DP, Palindromes: expand or table, Prefix segmentation DP, State-machine DP (stocks), Bitmask DP over subsets, Memoised DFS (top-down), Digit DP, Game DP (minimax on a range), Counting ways with modulo, DP over sorted keys (chains).