Skip to main content

Interval DP: Matrix Chain, Optimal BST, Balloon Burst

What This Concept Is​

Interval DP indexes contiguous ranges and combines smaller ranges. A split must make subproblems independent once their boundary information is fixed. Choose the last operation when choosing the first would change those boundaries. Increasing interval length is a common evaluation order, justified because every dependent interval is shorter.

Why It Matters Here​

The table shape is not the proof. Matrix chains, optimal search trees and balloon removal all use intervals, but they have different boundary semantics and costs. Importing a split recurrence without those details can optimize a different objective.

Concrete Examples​

Matrix chain. Matrices 0..n-1 have dimensions p[i] x p[i+1] with all dimensions positive. For inclusive interval [i,j], base M(i,i)=0 and:

M(i,j) = min over i<=k<j of
         M(i,k) + M(k+1,j) + p[i]*p[k+1]*p[j+1]

The last multiplication combines shapes p[i] x p[k+1] and p[k+1] x p[j+1]; this explains all three factors. Every parenthesization has one last split, and replacing either child preserves the boundary shape. For dimensions [10,30,5,60], (A0*A1)*A2 costs 1500+3000=4500; A0*(A1*A2) costs 9000+18000=27000. Store the winning k for reconstruction. There are O(n²) cells, O(n³) split work, and O(n) nodes in the output tree. The objective counts conventional scalar multiplications, not actual machine latency.

Optimal BST, successful searches only. For sorted keys with nonnegative query frequencies f[i], count root depth as 1. Let empty interval cost be 0. Choosing root r yields left cost + right cost + sum of all frequencies in the interval, because every key becomes one level deeper relative to an empty boundary. Prefix sums compute that interval total in O(1). This model omits unsuccessful searches; the full CLRS model includes gap frequencies and different base costs. Do not call them the same objective.

Balloon removal. Add fixed boundary values 1. Let B(i,j) optimize the open interval (i,j) while i,j stay present. If k is the last removed balloon, its final neighbors are exactly i,j: B(i,j)=max(B(i,k)+B(k,j)+a[i]*a[k]*a[j]). Empty intervals have value 0. For values [2,3], removing 2 then 3 scores 6+3=9; the reverse scores 6+2=8. Choosing the first removal would change adjacency and need a richer state.

Common Confusion / Misconceptions​

Some row orders are valid and others are not: saying all row-major orders fail is too broad. The obligation is dependency readiness. Arbitrary positive or negative cost functions do not automatically satisfy optimizations such as Knuth or divide-and-conquer monotonicity. Prove their extra hypotheses before reducing split ranges. A fast wrong range search can omit the true optimum.

How To Use It​

Fix open/closed interval notation and boundary conditions. Name the last operation, derive the combination cost from shapes or retained boundaries, and prove both directions. Count splits, record choices and independently evaluate the output tree. On tiny matrix chains enumerate all parenthesizations rather than comparing only with a second implementation of the same DP.

Check Yourself​

Why is matrix cost independent of how each child was parenthesized? Which frequency model is being used by the BST recurrence? Why does "last balloon" preserve the interval boundary?

Mini Drill or Application​

Dimensions [5,2,4,3]: compare both parenthesizations. Feedback: left-first costs 40+60=100; right-first costs 24+30=54. Return the tree (0,(1,2)), not a sorted list of matrix dimensions.

Read This Only If Stuck​

CLRS: matrix-chain multiplication and optimal binary search trees. Check the query frequency model before using an example from a different formulation.