Interval Dynamic Programming: Matrix Chain Multiplication, Burst Balloons & Optimal Substring Partitioning

Interval Dynamic Programming solves optimization problems defined over contiguous linear segments and ranges [i, j]. By organizing state transitions around interval length rather than index order, Interval DP models complex structural partitioning—from optimal compiler expression parsing and Matrix Chain Multiplication to Burst Balloons and polygon triangulation.

1. The Anatomy of Interval DP: Iteration by Segment Length

In classical grid DP, states depend on earlier coordinates (e.g., i - 1 or j - 1). In Interval DP, solving a range [i, j] requires combining the optimal solutions of smaller sub-ranges [i, k] and [k + 1, j] for all valid split points k ∈ [i, j - 1].

If an algorithm iterates over i and j in standard nested order, it will attempt to reference dp[k + 1][j] before it has been computed. Therefore, the canonical iteration invariant of Interval DP is looping over interval length L from 2 up to N:

for (int len = 2; len <= N; ++len) {          // Interval length
    for (int i = 1; i <= N - len + 1; ++i) {  // Left boundary
        int j = i + len - 1;                  // Right boundary
        for (int k = i; k < j; ++k) {         // Split point
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + cost(i, k, j));
        }
    }
}

Because len strictly increases, all sub-intervals of length < len are guaranteed to be fully resolved, preserving Bellman's principle of optimality.

2. Matrix Chain Multiplication (MCM): Parenthesization Optimization

Matrix multiplication is associative: (A × B) × C = A × (B × C). However, the order of parenthesization dramatically impacts scalar multiplication count. Multiplying matrix A (10 × 100), B (100 × 5), and C (5 × 50):

(A × B) × C: (10 × 100 × 5) + (10 × 5 × 50) = 5,000 + 2,500 = 7,500 scalar multiplications.
A × (B × C): (100 × 5 × 50) + (10 × 100 × 50) = 25,000 + 50,000 = 75,000 scalar multiplications (10x slower!).

Let p = [p0, p1, ..., pn] where matrix Ai has dimensions p[i-1] × p[i]. The minimum scalar multiplications dp[i][j] satisfies:

    dp[i][j] = min_{i ≤ k < j} (dp[i][k] + dp[k + 1][j] + p[i - 1] × p[k] × p[j])
  

With base case dp[i][i] = 0. Testing all k ∈ [i, j - 1] requires O(N) work per pair, resulting in O(N^3) total time and O(N^2) space.

3. Burst Balloons (LeetCode 312): The Reverse Thinking Breakthrough

In the Burst Balloons problem, bursting balloon i yields coins equal to nums[left] × nums[i] × nums[right], where left and right are adjacent remaining balloons.

Why Forward Simulation Fails

If we try to pick which balloon bursts first, the left and right subproblems become entangled because bursting a balloon merges previously separated neighbors. Subproblems lose independence, violating dynamic programming prerequisites.

The Reverse Breakthrough: We invert the formulation and ask: Which balloon k is burst LAST in range [i, j]?

Because balloon k is the very last to burst in [i, j], all other balloons in [i, j] have already been removed. Therefore, the immediate neighbors of k when it bursts are fixed as the non-burst boundary balloons i - 1 and j + 1:

    dp[i][j] = max_{i ≤ k ≤ j} (dp[i][k - 1] + dp[k + 1][j] + nums[i - 1] × nums[k] × nums[j + 1])
  

This decoupling ensures that subproblems [i, k - 1] and [k + 1, j] are 100% independent, cleanly solvable in O(N^3) time.

4. Knuth's Optimization: Quadrangle Inequality & O(N^2) Pruning

When the cost function satisfies the Quadrangle Inequality:

    cost[a][c] + cost[b][d] ≤ cost[a][d] + cost[b][c]        (for all a ≤ b ≤ c ≤ d)
  

The optimal split point opt[i][j] is monotonic: opt[i][j - 1] ≤ opt[i][j] ≤ opt[i + 1][j]. Instead of scanning all k ∈ [i, j - 1], we narrow the search window strictly to [opt[i][j - 1], opt[i + 1][j]]:

for (int len = 2; len <= N; ++len) {
    for (int i = 1; i <= N - len + 1; ++i) {
        int j = i + len - 1;
        int startK = opt[i][j - 1];
        int endK = opt[i + 1][j];
        for (int k = startK; k ≤ endK; ++k) {
            int val = dp[i][k] + dp[k + 1][j] + cost(i, j);
            if (val < dp[i][j]) {
                dp[i][j] = val;
                opt[i][j] = k;
            }
        }
    }
}

Summing the reduced loop iterations telescopingly reduces total runtime complexity from O(N^3) to O(N^2), enabling scaling to N ∼ 5,000.

5. Interval DP Archetypes Matrix

Problem Archetype	Decision Point k	Standard Complexity	Optimized Complexity	Optimization Mechanism
Matrix Chain Multiplication	Split parenthesization point	O(N^3)	O(N^2)	Knuth Monotonicity
Burst Balloons (LC 312)	Last balloon burst in range	O(N^3)	O(N^3)	Reverse Thinking Decoupling
Optimal Binary Search Tree	Root key of sub-tree [i, j]	O(N^3)	O(N^2)	Knuth Quadrangle Inequality
Polygon Triangulation	Intermediate triangle vertex	O(N^3)	O(N^3)	Catalan Structuring

6. Key Engineering Takeaways

Boundary Buffering: Always pad arrays with sentinel boundaries (e.g., adding nums[-1] = 1 and nums[N] = 1 in Burst Balloons) to prevent out-of-bounds branching.
State Memoization alternative: If recursion with memoization (top-down) is preferred over iteration by length (bottom-up), ensure states memo[i][j] are initialized to -1 to avoid re-evaluating zero-cost partitions.
Check Quadrangle Conditions: Always mathematically verify the Quadrangle Inequality before applying Knuth's optimization; non-convex cost functions yield invalid optimal split pruning.