1Understand
The idea
dp[i][j] is the answer for the range from i to j, built from smaller ranges inside it, often by trying every split point or the element handled last. Fill the table by increasing range length so smaller ranges are ready first, which typically costs O(n³).
Intuition
dp[i][j] is the answer for the range from i to j, built from smaller ranges inside it, often by trying every split point or the last element burst/removed.
Fill by increasing interval length so every shorter piece is already computed. That usually costs O(n³): O(n²) intervals times O(n) splits.
Burst balloons, matrix chain multiplication and optimal BSTs are the classic shapes.
What you will be able to do
- Iterate by increasing length
- Pick the right split variable
When to use it
- Answer for a range combines answers for sub-ranges
- Choose a split point or last operation
2See it
Walkthrough
Burst balloons, fill by length
vals = [_, 3, 1, 5, _], dp[l][r] uses shorter open intervals first.
1 / 4
Virtual borders •. dp[i][i+1] = 0 (no balloons strictly inside).
Live template
Line 1 active
Complexity: time O(n³), space O(n²)
Typical O(n³) time, O(n²) space. Fine for n ≤ 400-ish; too slow for n ~ 10³+. When intervals only need adjacent merges, sometimes O(n²) tricks exist, do not assume.
Read the walkthrough as text
Burst balloons (idea). Balloons [3,1,5,8] (with virtual 1s at borders).
dp[l][r]= max coins bursting open balloons strictly between l and r.- Try each k as the last burst in
(l,r): coins =vals[l]*vals[k]*vals[r] + dp[l][k] + dp[k][r]. - Length-2 intervals are 0 (nothing inside); grow length until
[0,n+1]. - Answer sits in
dp[0][n+1].
The "last burst" perspective makes subproblems independent.
3Recognise it
Kinds of problems (5)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Longest palindromic subsequence
Example. Longest palindrome subsequence length.
How. dp[i][j] on increasing length; match ends or take max of inner ranges.
Burst balloons (last operation)
Example. Max coins bursting all balloons.
How. dp[i][j] best on open (i,j); pick last balloon k between i and j as final burst.
Matrix chain multiplication
Example. Minimum scalar multiplications for chain of matrices.
How. Split k between i and j; combine left and right chain costs plus multiply cost.
Minimum cost to cut a stick
Example. Cut stick at marked positions, minimum total cut cost.
How. Interval DP on expanded coordinates; last cut in segment defines subproblems.
Two-player optimal play (stone game)
Example. Both play optimally on ends of pile.
How. dp[i][j] = max(pick left vs right) with opponent score implied by remainder.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Wrong fill order
Why it happens. Double for i,j can visit ranges before sub-ranges are ready.
How it fails. dp[i][j] uses dp[i][k] unset when length loop does not increase length first.
Fix. Outer loop on interval length; inner on start i with j=i+len-1.
Split bounds
Why it happens. Split k between i and j feels like any k works.
How it fails. k=j included in both subintervals, balloon burst counted twice.
Fix. Split range (i,j) open: k runs i+1 .. j-1 as last picked inside.
First vs last choice
Why it happens. First operation splits the problem the same way in your head.
How it fails. Matrix chain picks first multiply as split, left/right chains not independent.
Fix. Interval DP on “last operation” so subproblems are strictly inside.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.