Skip to content
Tutorials Center
My learning

Topics

Lesson 157 of 225 ยท Dynamic Programming

Interval and Matrix-Chain DP

Learn interval dynamic programming in Python: matrix-chain multiplication, burst balloons, merging stones and optimal BST with the split-point template.

Some problems ask about a range of items and the best way to combine them: in what order should you multiply a chain of matrices, which balloon should you pop last, how should you merge a row of stone piles. The subproblems are intervals [i, j], and the solution picks a split point k that divides the interval into two smaller intervals.

This is interval DP. It costs O(n^3) for most problems, which is fine up to n of a few hundred. You already met range tables in DP on strings (longest palindromic subsequence); here the transition gets a loop over split points.

The template

TEXT
dp[i][j] = best value for the interval from i to j

for length from 2 to n:               # smaller intervals first
    for i from 0 to n - length:
        j = i + length - 1
        dp[i][j] = best over k in [i, j) of
                   combine(dp[i][k], dp[k+1][j], cost of joining them)

Intervals of length 1 are the base cases. We loop by interval length so that when we compute dp[i][j], both halves (which are shorter) are already done.

TEXT
dp table (upper triangle only):

        j=0   j=1   j=2   j=3
 i=0    base  ...   ...   answer
 i=1          base  ...   ...
 i=2                base  ...
 i=3                      base
 fill diagonal by diagonal, from the main diagonal outward

There are O(n^2) intervals and each tries O(n) splits, so the time is O(n^3) and the space is O(n^2).

Matrix-chain multiplication

Multiplying a p x q matrix by a q x r matrix takes p x q x r scalar multiplications and gives a p x r matrix. Matrix multiplication is associative, so (A B) C and A (B C) give the same result, but the cost can differ enormously.

Take three matrices of sizes 10 x 30, 30 x 5 and 5 x 60:

TEXT
(A B) C : 10*30*5 + 10*5*60 = 1500 + 3000 = 4500
A (B C) : 30*5*60 + 10*30*60 = 9000 + 18000 = 27000

Problem. Given dimensions dims of length n + 1 (matrix i is dims[i] x dims[i+1]), find the cheapest parenthesization.

State. dp[i][j] = the minimum cost to multiply matrices i..j.

Transition. Split at k: multiply i..k and k+1..j separately, then multiply the two results. The left result is dims[i] x dims[k+1], the right is dims[k+1] x dims[j+1]:

TEXT
dp[i][j] = min over k of  dp[i][k] + dp[k+1][j] + dims[i] * dims[k+1] * dims[j+1]
dp[i][i] = 0

The brute force enumerates every parenthesization; the number of those is a Catalan number, which explodes. The DP is cubic.

Python Matrix-chain: minimum cost and order

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Burst balloons

Problem. You have balloons with values nums. Bursting balloon i earns left * nums[i] * right, where left and right are its current neighbors (out-of-range neighbors count as 1). Burst all balloons to maximize the coins.

The obvious approach, choosing which balloon to burst first, fails: after it is gone, its neighbors become adjacent and the two sides are no longer independent subproblems.

The trick is to reverse the thinking: choose which balloon to burst last in an interval. If balloon k is last in (i, j), its neighbors at that moment are exactly the borders i and j, and the balloons on each side were burst independently.

Pad the list with a 1 on both ends, then:

TEXT
dp[i][j] = max over k in (i, j) of dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]

where dp[i][j] is the best coins from bursting everything strictly between i and j.

Python Burst balloons

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For [3, 1, 5, 8] the best order yields 167 coins. The pattern "think about the last action instead of the first" is a standard way to split a problem into independent halves.

Merging stones in a line

Problem. Piles of stones are in a row. Merging two adjacent piles costs the sum of their sizes and creates one pile. Find the minimum total cost to merge everything into one pile.

State. dp[i][j] = minimum cost to merge piles i..j into one. The last merge joins a left part i..k and a right part k+1..j, and costs the total weight of i..j (use a prefix sum for that in O(1)):

TEXT
dp[i][j] = min over k of dp[i][k] + dp[k+1][j] + sum(i..j)
Python Merging stones, minimum cost

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

If you may merge any two piles (not only adjacent ones), the problem becomes greedy and is solved with a heap, exactly like Huffman coding. The adjacency rule is what forces interval DP.

Optimal binary search tree

Suppose keys are searched with known frequencies. Which binary search tree minimizes the expected number of comparisons? Putting a frequent key near the root is good, but the shape must stay a valid BST.

State. cost[i][j] = minimum weighted search cost of a BST holding keys i..j.

Transition. Choose a root r in i..j. Then the left subtree holds i..r-1, the right holds r+1..j, and every key sits one level deeper, which adds the total frequency of i..j once:

TEXT
cost[i][j] = min over r of cost[i][r-1] + cost[r+1][j] + sum of freq[i..j]

This is the same split-point template again. (A refinement by Knuth shows the best root moves monotonically, reducing the time to O(n^2), but the cubic version is the one to learn first.)

Python Optimal BST cost

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Palindrome partition as interval DP

DP on strings solved minimum palindrome cuts with a prefix state. Here is the same question expressed as an interval: cuts[i][j] = minimum cuts to split s[i..j] into palindromes. It is 0 if the whole range is a palindrome, else the best cuts[i][k] + cuts[k+1][j] + 1. It works, but costs O(n^3); the prefix version is better. The lesson: the same problem can often be modelled with several states, and a smaller state means a faster algorithm.

Choosing between prefix, range and interval states

  • If the answer for a prefix only depends on shorter prefixes (word break, LIS), use a prefix state.
  • If you must combine two independent pieces and the pieces are contiguous ranges, use interval DP.
  • If removing an element changes its neighbors (balloons), look for the last operation.

Common mistakes

  • Looping i and j in the wrong order. Interval DP needs shorter intervals first, so loop by length (or i downward).
  • Wrong cost term. For matrix chain it is dims[i] * dims[k+1] * dims[j+1], not dims[k].
  • Choosing the first balloon instead of the last.
  • Off-by-one in split loops. In [i, j], k ranges over i..j-1 when the halves are [i, k] and [k+1, j].
  • Expecting speed. O(n^3) with n = 1000 is a billion steps. Check the constraints.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the time complexity of the standard interval DP?

    There are O(n^2) intervals, and each one tries O(n) split points.
  2. 2. Why does burst balloons choose the LAST balloon to burst in an interval?

    If you pick the first balloon, its removal makes neighbors adjacent and couples the sides. A last balloon sees only the borders.
  3. 3. What is the cost of (A B) C for sizes 10x30, 30x5 and 5x60?

    A B costs 10305 = 1500 and yields a 10x5 matrix; multiplying by C costs 10560 = 3000. The total is 4500.
  4. 4. In which order should an interval DP table be filled?

    dp[i][j] needs smaller intervals inside it, which have shorter lengths.
  5. 5. Why is merging stones with ANY two piles easier than merging only adjacent ones?

    Without the adjacency rule, always merging the two smallest piles is optimal. Adjacency forces the interval DP.

Summary

  • Interval DP solves problems on contiguous ranges by choosing a split point and combining two smaller ranges.
  • Fill the table by increasing interval length; the cost is O(n^3) time and O(n^2) space.
  • Matrix chain: dp[i][j] = min(dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1]).
  • Burst balloons: pick the last balloon of an interval so the sides become independent.
  • Merging adjacent stones and optimal BSTs use the same template with a prefix-sum range weight.
  • Next to the cubic template, look for a better state if n is large.

Next: Bitmask DP