Chapter 5: Interval DP

Some dynamic programming problems are not indexed by a single position or a grid cell — they are indexed by a range. The subproblem is “what is the optimal answer for the contiguous segment from index i to index j?” Written as dp[i][j], this pattern appears whenever you must decide how to split or merge a sequence.

Classic triggers include matrix parenthesization, bursting balloons, palindrome partitioning, and optimal binary search trees. The unifying question is: where do I cut this interval? You try every split point k between i and j, combine optimal answers from the left piece [i, k] and right piece [k+1, j], and take the best.

Matrix Chain Multiplication

Given a chain of matrices A₀, A₁, …, Aₙ₋₁ where matrix Aᵢ has dimensions dims[i] × dims[i+1], find the minimum number of scalar multiplications needed to compute the product. The order of multiplication matters enormously: for three matrices, (AB)C and A(BC) can have vastly different costs.

Define dp[i][j] as the minimum cost to multiply matrices i through j. The base case is dp[i][i] = 0 — a single matrix needs no work. For longer intervals, try every split k:

dp[i][j] = min over k in [i, j-1] of:
    dp[i][k] + dp[k+1][j] + dims[i] * dims[k+1] * dims[j+1]

The last term is the cost of multiplying the two resulting matrices.

Diagonal Fill Order

Interval DP has a fill order unlike anything you have seen so far. You cannot fill row-by-row or left-to-right — you must fill by interval length, starting with length 1 (the diagonal), then length 2, then 3, and so on. When computing dp[i][j], every sub-interval dp[i][k] and dp[k+1][j] must already be filled, which means all shorter intervals must come first.

Fill order for n=4 matrices (indices 0..3):

Length 1:  dp[0][0] dp[1][1] dp[2][2] dp[3][3]   ← diagonal
Length 2:  dp[0][1] dp[1][2] dp[2][3]             ← one above diagonal
Length 3:  dp[0][2] dp[1][3]
Length 4:  dp[0][3]                               ← answer cell

This diagonal sweep is the signature of interval DP.

Burst Balloons

LeetCode 312: You have balloons with values nums[i]. Bursting balloon i gives coins equal to nums[i-1] × nums[i] × nums[i+1] (with boundary balloons of value 1). Burst all balloons to maximize total coins.

The forward-thinking approach fails — the order of bursting changes which neighbors exist. The breakthrough is reverse thinking: instead of asking “which balloon do I burst first?”, ask “which balloon do I burst last?” If balloon k is the last one burst in range [i, j], then at that moment its neighbors are fixed: nums[i-1] and nums[j+1] (using padded boundaries). The subproblems on the left and right become independent.

Pad with 1 at both ends: [1, nums[0], nums[1], ..., nums[n-1], 1]

dp[i][j] = max coins from bursting all balloons in original range i..j

For each k in [i, j] as the LAST balloon burst:
  coins = dp[i][k-1] + dp[k+1][j] + padded[i] * padded[k+1] * padded[j+2]

(In code with 0-indexed padded array, k is the last burst index in the open interval.)

Notice the same interval structure and diagonal fill order as matrix chain. The difference is the interpretation of k: split point for multiplication versus last-burst balloon for coins.

Summary

• State: dp[i][j] = optimal answer for range [i, j]
• Transition: try every split/last-choice k in the range
• Fill order: by interval length (diagonal sweep)
• Answer: dp[0][n-1]
• Time: O(n³) for a sequence of length n