Interval DP
Solve a question about every stretch of a sequence, short stretches first, by trying every place to split each stretch in two.
O(n³)Space O(n²)6 practice problemsStep-through pictureThe idea
Interval DP answers a question for every interval of a sequence: every stretch from index left to index right. The answers for short intervals are combined into answers for longer ones, until you reach the whole sequence.
The usual transition tries every split point. For the interval left..right, pick a split between them, solve left..split and split + 1..right, and combine. The best split wins. Because both halves are shorter, their answers are already in the table if you fill it by interval length.
The template merges a row of bundle files into one. Merging two neighboring bundles costs their combined size, and you want the cheapest order of merges.
An everyday example
Gluing a row of paper strips
You have a row of paper strips of different lengths and you can only glue two neighbors together. Each glue job costs as much as the length of the two strips together. To plan the cheapest gluing of the whole row, think about the very last glue job: it joins a left part and a right part. Try every place where the row could split into those two parts, and use the best plans you already made for the shorter parts.
| In the example | In the code |
|---|---|
| The row of strips | The sizes array |
Cheapest way to glue strips left to right into one | cost[left][right] |
| Where the last glue job joins two parts | split |
| Cost of gluing both parts first | cost[left][split] + cost[split + 1][right] |
| The last glue job itself | The total size from left to right |
From the slow way to interval dp
- Start with brute force: try every order of merges, add up the cost of each order, and keep the cheapest. The number of orders grows like the Catalan numbers: a row of 10 bundles has 4,862 different merge trees, and a row of 20 has 1,767,263,190.
- A simple rule doesn't save you. For
sizes = [7, 5, 6, 7], "always merge the cheapest neighbor pair" merges 5 and 6 first and pays 54 in total, while merging7 + 5and6 + 7first pays only 50. You need to compare real options, but without listing every order. - Look at the very last merge. It joins two bundles: one made from bundles
lefttosplit, and one made fromsplit + 1toright, for somesplit. The last merge always costs the total size of the whole stretch, whatever happened before. And the two halves were built independently: no merge ever crosses the split. So the cheapest total is the cheapest left half, plus the cheapest right half, plus the total size. - Each half is itself a stretch, so the state is an interval:
cost[left][right]. There are only aboutn² / 2intervals. An interval only reads shorter intervals, so fill them by length: all length 2, then length 3, and so on. That loop over lengths, starts, and splits is interval DP.
How it works
- Precompute
prefixsums so the total size of any interval isprefix[right + 1] - prefix[left]. - Make
cost, annbyntable. Intervals of one bundle cost0: there is nothing to merge. - Loop over interval lengths
lenfrom 2 ton, so every shorter interval is already solved. - For each
left, setright = left + len - 1and try everysplitfromlefttoright - 1. - Each split costs
cost[left][split] + cost[split + 1][right]; keep the smallest. - Add the cost of the final merge, which is the total size of the interval.
- The answer is
cost[0][n - 1], the whole row.
Watch it run
This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.
See every step at onceThe same run, laid out side by side
The code
Point at a note to light up the lines it explains.
function cheapestMerge(sizes) {const n = sizes.length;if (n === 0) return 0;const prefix = [0];for (const size of sizes) prefix.push(prefix[prefix.length - 1] + size);const cost = Array.from({ length: n }, () => new Array(n).fill(0));for (let len = 2; len <= n; len++) {for (let left = 0; left + len - 1 < n; left++) {const right = left + len - 1;cost[left][right] = Infinity;for (let split = left; split < right; split++) {const total = cost[left][split] + cost[split + 1][right];cost[left][right] = Math.min(cost[left][right], total);}cost[left][right] += prefix[right + 1] - prefix[left];}}return cost[0][n - 1];}
How fast it is
| Time | O(n³) |
|---|---|
| Extra memory | O(n²) |
About n²/2 intervals, each trying up to n split points. The table holds one number per interval.
- Best case
O(n³)Any row: every interval tries every split, whatever the sizes are.
- Average case
O(n³)Any row: about
n³ / 6split checks in total. For 4 bundles that is 10, as in the trace. - Worst case
O(n³)The same. For 200 bundles it is 1,333,300 split checks, which is fast; for 2,000 it is over 1.3 billion, which is too slow.
Common mistakes
- Filling the table row by row from the top, so a cell reads a longer or later interval that is still empty. Loop by length.
- Using a greedy rule such as "always merge the two smallest neighbors". It can miss the best order; check every split.
- Forgetting the cost of the final merge, or adding it inside the split loop so it counts once per split.
- Off-by-one errors in
split: the left part isleft..splitand the right part issplit + 1..right, sosplitstops atright - 1.
When to use it
Look for these clues in a problem:
- Items can only be combined with their neighbors, and the order of combining changes the cost.
- The question is about the best way to split, merge, or remove items from a row, where what's left joins up.
- A sequence is read from both ends, such as two players taking items from either end.
- The input is small, up to a few hundred items, which suggests an
O(n^3)solution.
Check yourself
Answer each one in your head first, then open it.
Why must the table be filled by interval length?
An interval reads two shorter ones, which might start later or end earlier than it. Filling by length is the simple order that guarantees all shorter intervals are finished first.
Why is the total size added once, after the split loop?
The final merge costs the same total for every split, so it doesn't change which split wins. Adding it once after the loop counts it exactly once; adding it to cost[left][right] inside the loop would count it once per split.
How many split checks does the code make for 5 bundles?
20: 4 intervals of length 2 with 1 split, 3 of length 3 with 2, 2 of length 4 with 3, and 1 of length 5 with 4.
Why doesn't the greedy Huffman method work here?
Huffman may merge any two bundles, even far apart. Here only neighbors can merge, so the two smallest bundles might not be next to each other.
Practice problems
Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.
0 of 6 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.
Start practicingGo further
You don't need these to start practicing. Open one when you want more.
Why it works
The reasoning that makes it always right
The table keeps one promise: when the loops start on length len, every interval shorter than len holds its cheapest merge cost. Intervals of length 1 cost 0, which the table starts with, so the promise holds before length 2.
Filling an interval keeps the promise. In any merge order for bundles left to right, the final merge joins the bundle built from left..split with the one built from split + 1..right, for some split. The final merge costs the total size, which doesn't depend on the order. The two halves are built separately, and in a cheapest order each half must be built as cheaply as possible; otherwise swapping in a cheaper way for that half would lower the total. So the answer is the best split's two half costs plus the total, which is what the code computes.
Both halves are shorter than the interval, so filling by length means they are always ready. The prefix sums give the total size of any interval in one subtraction. After the last length, the promise covers the whole row, cost[0][n - 1].
Going deeper
4 more ideas
What each cell of the table means
cost[left][right] is the cheapest total cost to merge bundles left through right into one bundle. Only cells with left <= right are used, so the table is a triangle above the diagonal. The diagonal cells are single bundles and cost 0.
Why the fill order is by length
A cell reads intervals that are strictly shorter. Filling all length-2 intervals, then all length-3, and so on, guarantees the parts are ready. A plain row-by-row loop would read cells below it that are not filled yet.
How much work it does
There are about n * n / 2 intervals and each tries up to n splits, so the time is O(n^3) and the table uses O(n^2) space. For n = 200, that is about 1.3 million steps, which is fast.
Other shapes of interval DP
Not every interval DP splits. For the longest palindromic subsequence, best[left][right] looks only at best[left + 1][right - 1], best[left + 1][right], and best[left][right - 1]. For games where players take from either end, the cell is the best score difference for the player to move.
Work it by hand
Every step in a table, with why
Merge 4 bundles in a row into one, where each merge costs the combined size. Each row fills one interval of cost.
sizes = [4, 2, 3, 1], so prefix = [0, 4, 6, 9, 10]
| Step | len | left..right | Splits tried | Size added | cost[left][right] | What happens | Why |
|---|---|---|---|---|---|---|---|
| 1 | 2 | 0..1 | split 0: 0 | 6 | 6 | Merge 4 and 2 | Two single bundles cost nothing to build, so the only cost is the merge itself: 4 + 2. |
| 2 | 2 | 1..2 | split 1: 0 | 5 | 5 | Merge 2 and 3 | Same as above for the middle pair. |
| 3 | 2 | 2..3 | split 2: 0 | 4 | 4 | Merge 3 and 1 | All length-2 intervals are done, so length 3 can read them. |
| 4 | 3 | 0..2 | 0: 5, 1: 6 | 9 | 14 | Best split after index 0 | Building [2, 3] first (5) beats building [4, 2] first (6). Then the final merge of size 9 is added. |
| 5 | 3 | 1..3 | 1: 4, 2: 5 | 6 | 10 | Best split after index 1 | Merging 3 and 1 first (4) is cheaper than merging 2 and 3 first (5). |
| 6 | 4 | 0..3 | 0: 10, 1: 10, 2: 14 | 10 | 20 | Tie between two splits | Splits 0 and 1 both cost 10, so Math.min keeps 10. The final merge of all 10 units makes 20. Line 18 returns it. |
It returns 20. One cheapest order is: merge 4 and 2 (6), merge 3 and 1 (4), then merge the two results (10). The loops end after the one interval of full length.
Compared with other ways
When to pick something else
| Approach | Time | Extra memory | Choose it when |
|---|---|---|---|
| Interval DP | O(n³) | O(n²) | Merges or operations only happen between neighbors, and n is up to a few hundred. |
| Interval DP with Knuth's optimization | O(n²) | O(n²) | The cost rule allows it, and n is in the thousands. |
| Greedy smallest pair (Huffman) | O(n log n) | O(n) | Any two bundles may be merged, not only neighbors. Then always merging the two smallest is provably best. |
| Try every merge order | O(4^n) | O(n) | Only to check answers on rows of 8 or fewer. |
Extra memory: O(n²) for the cost table, of which only the upper triangle is used, plus O(n) for prefix.
How the steps grow
- Interval DP
O(n³) - Interval DP with Knuth's optimization
O(n²) - Greedy smallest pair (Huffman)
O(n log n) - Try every merge order
O(4^n)
| Approach | n = 10 | n = 1,000 | n = 1,000,000 |
|---|---|---|---|
| Interval DP | 1,000 | 1 billion | more than a quadrillion |
| Interval DP with Knuth's optimization | 100 | 1 million | 1 trillion |
| Greedy smallest pair (Huffman) | 33 | 9,966 | 20 million |
| Try every merge order | 1 million | more than a quadrillion | more than a quadrillion |
Inputs that need care
5 tricky inputs
- An empty row:
sizes = [] - Line 3 returns 0 before any table is made.
- One bundle:
sizes = [7] - The length loop starts at 2, which is more than
n, so it never runs. It returnscost[0][0], which is 0: nothing to merge. - Two bundles:
sizes = [5, 8] - One interval, one split, cost
0 + 0 + 13 = 13. - Equal sizes:
sizes = [2, 2, 2, 2] - Many splits tie, and
Math.minkeeps the shared value. The answer is 16: two pairs of 4, then 8. - Bundles of size 0
- They work as they are: merging them adds 0 for their part. The prefix sums still give the right totals.
Variations and follow-ups
Twists interviewers add
Matrix chain order
Multiplying a chain of matrices has the same shape: the last multiplication splits the chain in two. The cost of that last step depends on the sizes at left, split + 1, and right + 1, instead of a total.
Choosing the last item instead of a split
For popping balloons where each pop scores using its neighbors, ask which balloon in an interval is popped last. Its neighbors at that moment are the interval's outer edges, so the two sides are independent, just like halves.
Intervals without splits
The longest palindromic subsequence fills best[left][right] from best[left + 1][right - 1] when the ends match, or the larger of dropping either end. Games where two players take from either end use the same interval states for the score difference.
Faster splits
For some cost rules, including this merge cost, the best split for an interval lies between the best splits of its two slightly shorter intervals. Searching only that range is Knuth's optimization and brings the time down to O(n²).
In an interview
Spot it, explain it, answer follow-ups
- Spot it when the problem works on a row where only neighbors can combine, or asks about every substring or subarray of a sequence: merging stones, bracketing, cutting a stick, palindromes.
- Explain it by the last step: "the last merge splits the row in two, and the two sides don't affect each other". That one sentence justifies the whole recurrence.
- Test on a row of 3, where only two orders exist, and check both by hand. Then point out why you loop by length, not by row.
- Expect "can you write it top-down?". Yes: a memoized
solve(left, right)that tries every split. It is often easier to write, and it skips intervals that are never needed.
Where frontend code uses it
The same idea in real UI code
- Planning how to combine neighboring code chunks or CSS files, where each combine step has a cost based on size, is an interval DP when only neighbors can be joined.
- Checking which parts of a string are palindromes, used in some text tools and puzzles, fills an interval table of
leftandrightpositions. - Turn-based games in the browser where players take cards from either end of a row are solved with an interval table of best score differences.