Pattern Reference
Interval DP
"DP over intervals: matrix chain multiplication, burst balloons, palindrome partitioning II, stone game, optimal BST."
Loading...
Deep Dive Tutorial
Interval DP problems have a recursive structure: the answer for range [i,j] depends on answers for smaller ranges within [i,j]. The key insight is the "last operation" trick: instead of thinking about what to do first, think about what to do LAST. The last operation divides [i,j] into independent subproblems.
The Universal Template
Interval DP template — O(n³)
// dp[i][j] = best answer for subproblem on arr[i..j]
// Fill by increasing interval length
const n = arr.length;
const dp = Array.from({length: n}, () => new Array(n).fill(0));
// Base case: length-1 intervals (single elements)
for (let i = 0; i < n; i++) dp[i][i] = baseCaseValue(i);
// Build up from length 2 to n
for (let len = 2; len <= n; len++) {
for (let i = 0; i <= n - len; i++) {
const j = i + len - 1;
dp[i][j] = WORST_VALUE; // -Infinity or +Infinity
// Try every split point k
for (let k = i; k < j; k++) {
// k is the "last operation" split point
const candidate = combine(dp[i][k], dp[k+1][j], k);
dp[i][j] = bestOf(dp[i][j], candidate);
}
}
}
return dp[0][n-1];
// The "last operation" variants:
// k is the last balloon burst in [i,j] → dp[i][k] + value(k) + dp[k][j]
// k is where we split the matrix chain → dp[i][k] + dp[k+1][j] + cost(i,k,j)
// k is the partition point → dp[i][k] + dp[k+1][j] + cost(i,j)| Problem | What k represents | Combine formula |
|---|---|---|
| Burst Balloons | Last balloon to burst in [i,j] | dp[i][k] + nums[i]*nums[k]*nums[j] + dp[k][j] |
| Matrix Chain Mult. | Where to split the chain | dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1] |
| Palindrome Partition | Length of last palindrome piece | dp[i][k-1] + 1 if s[k..j] is palindrome |
| Min Cost Merge Stones | Where to merge last two groups | dp[i][k] + dp[k+1][j] + sum(i,j) |
| Strange Printer | Last character group printed | dp[i][k] + dp[k+1][j] - (s[k]===s[j] ? 1 : 0) |
Worked Problems
brain
Interval DP checklist:
1. Can the problem be expressed as "best answer for range [i..j]"?
2. Can it be split at a point k into independent subproblems?
3. Does "last operation" reversal simplify dependencies?
Fill order is critical: always fill by INCREASING interval length. Length 1 first (base), then 2, then 3, ..., up to n. This ensures dp[i][k] and dp[k+1][j] are ready when needed.
Complexity: O(n³) — n² intervals × O(n) split points. Acceptable for n ≤ 500.
1. Can the problem be expressed as "best answer for range [i..j]"?
2. Can it be split at a point k into independent subproblems?
3. Does "last operation" reversal simplify dependencies?
Fill order is critical: always fill by INCREASING interval length. Length 1 first (base), then 2, then 3, ..., up to n. This ensures dp[i][k] and dp[k+1][j] are ready when needed.
Complexity: O(n³) — n² intervals × O(n) split points. Acceptable for n ≤ 500.