Dynamic Programming

Interval DP

State is a range [i, j]: palindromic subsequences, burst balloons, matrix chain.

Hard, optional depth, about 120 minutes to practise.

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

•
3
1
5
•
01234

Virtual borders •. dp[i][i+1] = 0 (no balloons strictly inside).

for length in range(2, n+2):

Live template

Line 1 active

1for length in range(2, n + 1):
2 for i in range(n - length + 1):
3 j = i + length - 1
4 dp[i][j] = best(dp[i][k] + dp[k + 1][j] + cost(i, k, j) for k in range(i, j))

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).

  1. dp[l][r] = max coins bursting open balloons strictly between l and r.
  2. Try each k as the last burst in (l,r): coins = vals[l]*vals[k]*vals[r] + dp[l][k] + dp[k][r].
  3. Length-2 intervals are 0 (nothing inside); grow length until [0,n+1].
  4. 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.

All lessons