Pattern Guide
Matrix Chain & Generalized Interval DP
"Optimal parenthesization, burst balloons, stone merging. O(n³) interval DP."
Matrix chain multiplication and its generalizations: given a sequence of items, find the optimal way to combine adjacent pairs. dp[i][j] = optimal cost to combine items[i..j]. Transition: for each split point k, dp[i][j] = min over k in [i..j-1] of (dp[i][k] + dp[k+1][j] + cost(i,k,j)). Applications: matrix chain, burst balloons, stone game, remove boxes.
Problems you can solve with this pattern
3 problems · click any to start solving
// Matrix chain multiplication — minimum scalar multiplications
function matrixChain(dims) {
const n = dims.length - 1; // n matrices
// Matrix i has dimensions dims[i] x dims[i+1]
const dp = Array.from({length: n}, () => new Array(n).fill(0));
for (let len = 2; len <= n; len++) {
for (let i = 0; i + len - 1 < n; i++) {
const j = i + len - 1;
dp[i][j] = Infinity;
for (let k = i; k < j; k++) {
const cost = dp[i][k] + dp[k+1][j] + dims[i] * dims[k+1] * dims[j+1];
dp[i][j] = Math.min(dp[i][j], cost);
}
}
}
return dp[0][n-1];
}Interval DP template: compute dp[i][j] for increasing lengths. For length 1: base case. For length > 1: try all split points k. dp[i][j] = optimal combination of dp[i][k] and dp[k+1][j] plus the cost of merging the two parts. Burst balloons trick: think about the LAST balloon to burst in the range [i..j], not the first. This avoids dependency issues.
// Matrix chain multiplication — minimum scalar multiplications
function matrixChain(dims) {
const n = dims.length - 1; // n matrices
// Matrix i has dimensions dims[i] x dims[i+1]
const dp = Array.from({length: n}, () => new Array(n).fill(0));
for (let len = 2; len <= n; len++) {
for (let i = 0; i + len - 1 < n; i++) {
const j = i + len - 1;
dp[i][j] = Infinity;
for (let k = i; k < j; k++) {
const cost = dp[i][k] + dp[k+1][j] + dims[i] * dims[k+1] * dims[j+1];
dp[i][j] = Math.min(dp[i][j], cost);
}
}
}
return dp[0][n-1];
}Burst balloons trick: Think about the LAST item removed, not the first. This ensures the two subproblems dp[i][k] and dp[k][j] are independent (k is not yet removed when we compute them).
Complexity: O(n³) — n² intervals × n split points. Feasible for n ≤ 500. For n > 500, need Knuth-Yao optimization (requires monotone optimality condition) to get O(n²).