Pattern Guide
Interval DP
"dp[i][j] = best answer for subproblem on range [i..j]."
Interval DP solves problems over contiguous ranges by building up from small intervals to large ones. Burst Balloons, Matrix Chain Multiplication, Palindrome Partitioning, Strange Printer, and Minimum Cost to Merge Stones all follow the same template: dp[i][j] = best over all split points k in [i,j].
Problems you can solve with this pattern
5 problems · click any to start solving
// 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)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
// 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) |
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.