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

Interval Dynamic Programming solves optimization problems defined over contiguous ranges $[i, j]$. The key insight is iterating by interval length rather than index order, ensuring that all sub-intervals of smaller lengths are fully solved before evaluating larger envelopes.

1. Standard Interval DP Iteration Template

To ensure valid topological dependencies, interval DP must iterate over the interval length $L$ from $1$ to $N$:

for (int len = 1; len <= n; ++len) {
    for (int i = 0; i + len - 1 < n; ++i) {
        int j = i + len - 1;
        // Evaluate split points k between i and j
        for (int k = i; k < j; ++k) {
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + cost(i, k, j));
        }
    }
}

2. Reverse Thinking: LeetCode 312 Burst Balloons

In Burst Balloons, popping balloon $k$ causes its left and right neighbors to touch, breaking subproblem independence. By reversing our perspective and considering balloon $k$ as the last balloon to burst in range $(i, j)$, subproblems $(i, k)$ and $(k, j)$ remain completely independent.