Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Given matrix dimensions p[0..n] (matrix i is p[i-1] × p[i]), find the parenthesization that minimizes scalar multiplications. The recurrence splits the chain i..j at every k: dp[i][j] = min over k in i..j-1 of dp[i][k] + dp[k+1][j] + p[i-1]·p[k]·p[j]. dp[i][i] = 0. Naive recursion is exponential; memoize on (i, j) or fill the table by increasing chain length. O(n³) time, O(n²) space.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you recognize an interval-DP structure, set the state as a range [i, j], split on the last (outermost) operation, and order the table fill by increasing length so dependencies are ready.
Where candidates slip
Mangling the merge-cost index (using the wrong p[] triple), or filling the table in plain i,j order so dp[i][k] / dp[k+1][j] aren't computed yet.
How to stand out
Say 'I'll split on the last multiplication, k, which makes the two sides independent intervals'. Derive the p[i-1]·p[k]·p[j] cost from the shapes, then fill by chain length and mention this is the canonical interval-DP template.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewCheapest way to multiply a chainState is an interval [i,j]?Yes, split on kNo, per-elementExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 3
Brute Force — Recursion Over the Outermost Split
1Hint 1Explore hintHide hint
Don't think about which multiplication happens first — think about which happens LAST. The last multiply combines a left group A_i..A_k with a right group A_{k+1}..A_j.
2Hint 2Explore hintHide hint
For a fixed last split at k, the cost is (best way to multiply the left group) + (best way to multiply the right group) + the cost of combining the two resulting matrices.
3Hint 3Explore hintHide hint
The left result is p[i-1] × p[k], the right is p[k] × p[j]; combining them costs p[i-1]·p[k]·p[j]. Take the min over all k in i..j-1. Base: solve(i, i) = 0.
A · Core idea
Define solve(i, j) as the minimum cost to multiply matrices i..j. The key decision is the outermost (last) multiplication: pick a split point k between i and j-1, which means you first compute the product of A_i..A_k (a matrix of shape p[i-1] × p[k]), then the product of A_{k+1}..A_j (shape p[k] × p[j]), and finally multiply those two results together at cost p[i-1] · p[k] · p[j]. The answer for (i, j) is the minimum of that over all valid k. The base case is solve(i, i) = 0 — one matrix needs no work.
The mental shift: choose the LAST multiplication, not the first. This is the move that makes interval DP click. If you tried to pick the first multiplication, the two halves wouldn't be independent — the result of one feeds the next in a tangled way. But fixing the outermost split k cleanly partitions the chain into two contiguous sub-chains [i, k] and [k+1, j] that can be solved completely independently, then merged with one well-defined cost.
Where the merge cost comes from. After fully multiplying the left group you have a single matrix of dimensions p[i-1] × p[k] (its row count is the first matrix's rows, its column count is the k-th matrix's columns). The right group collapses to p[k] × p[j]. Multiplying an (p[i-1] × p[k]) by a (p[k] × p[j]) matrix costs p[i-1] · p[k] · p[j] scalar multiplications — that's the single term you add at this level.
Why min. Different k values are alternative bracketings of the same product; we want the cheapest, so we combine with min.
Why we don't ship this. The same interval (i, j) is re-solved inside many different outer splits — massive overlap. Cache solve(i, j) and the exponential collapses to O(n³).
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
p = [10, 20, 30, 40] (A1 10×20, A2 20×30, A3 30×40)solve(1,1), solve(2,2), solve(3,3)
single matrices
all 018000C · Code with teaching comments
Reference implementation previewpublic int matrixChain(int[] p) { int n = p.length - 1; return solve(p, 1, n); } Explore the full codeHide the full code
D · Why it works and complexityO(2ⁿ) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
Two index variables (i, j) describe the state — a contiguous interval — and the naive tree recomputes the same interval through different outer splits. A 2-D interval state plus exponential overlap is the textbook signal for an O(n³) interval DP.
ComplexityO(2ⁿ) time, O(n) space — Each interval branches into up to (j - i) splits, and the splits overlap heavily; the number of distinct parenthesizations is the Catalan number, which grows like 4ⁿ/n^1.5 — exponential. Recursion depth is O(n).
E · Edge cases and pitfalls4single matrix (n = 1) — solve(1, 1) returns 0 immediately — nothing to multiply.Explore edge casesHide edge cases
Edge cases handled
single matrix (n = 1)solve(1, 1) returns 0 immediately — nothing to multiply.
Pitfalls
- Splitting on the first multiplication instead of the last — the halves stop being independent.
- Getting the merge-cost triple wrong — it must be p[i-1]·p[k]·p[j], the rows/shared/cols of the two assembled matrices.
- Skipping this approach — the split-on-k recurrence is exactly what the interviewer wants verbalized.
Approach 2 of 3
Top-Down Memoization on (i, j)
1Hint 1Explore hintHide hint
solve(i, j) returns the same value every call. Where can you store it so each interval is computed once?
2Hint 2Explore hintHide hint
Use a 2-D memo of size (n+1) × (n+1) indexed by interval endpoints. Check on entry, fill before returning.
3Hint 3Explore hintHide hint
memo[i][j] = min over k of solve(i,k) + solve(k+1,j) + p[i-1]·p[k]·p[j]; use -1 (or 0 only on the diagonal) to mark 'uncomputed'.
A · Core idea
Keep the split-on-k recurrence but cache solve(i, j) in a 2-D table so every interval is solved exactly once. The memo starts 'uncomputed'; on entry we return the cached value and store the result before returning.
The mental shift: the cost of an interval depends only on its endpoints. No matter which outer splits led you to consider matrices i..j, the cheapest way to multiply that contiguous block is a fixed number. So caching by (i, j) collapses all the duplicate subtrees. There are O(n²) intervals, and each costs O(n) to resolve (scan the splits), giving the O(n³) bound directly.
Why the state is two indices, not one. Unlike Coin Change (one number), an interval needs both a left and a right boundary — different ranges of the same length have different costs because the dimensions inside them differ. That's why the memo is 2-D.
Choosing the sentinel. Initialize the memo to -1 for 'uncomputed' (0 is a valid cost only on the diagonal, so guarding i == j separately or using -1 keeps things unambiguous).
A language note. Top-down recursion here nests up to O(n) deep. In Java that's fine for n ≤ 100. In Python the default recursion limit is about 1000 and the per-call overhead is higher — for large chains the bottom-up table (next approach) is the cleaner default because it visits intervals in a guaranteed-ready order without any stack.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
p = [40, 20, 30, 10, 30] (4 matrices)diagonal
memo[i][i] = 0 for all i
base cases26000C · Code with teaching comments
Reference implementation previewpublic int matrixChain(int[] p) { int n = p.length - 1; int[][] memo = new int[n + 1][n + 1]; for (int[] row : memo) { Arrays.fill(row, -1);Explore the full codeHide the full code
D · Why it works and complexityO(n³) timeO(n²) spaceOpen the invariant and proofExplore the proofHide the proof
Same mechanical DP upgrade: a correct recurrence plus a cache keyed on the true state, here the interval (i, j). The intellectual work was seeing that the outermost split makes the two halves independent intervals — once that clicks, the 2-D memo and its O(n³) cost follow mechanically.
ComplexityO(n³) time, O(n²) space — There are O(n²) distinct intervals (i, j). Each does O(n) work scanning split points → O(n³) total. The memo is O(n²); recursion depth is O(n) on top.
E · Edge cases and pitfalls5two matrices — Only k = 1 exists; memo[1][2] = p[0]·p[1]·p[2], one multiplication.Explore edge casesHide edge cases
Edge cases handled
two matricesOnly k = 1 exists; memo[1][2] = p[0]·p[1]·p[2], one multiplication.single matrixsolve(1, 1) returns 0 without touching the memo.
Pitfalls
- Choosing a sentinel that a real cost could equal — costs are ≥ 0, so use -1, and let the i==j base return 0.
- Sizing the memo as n×n instead of (n+1)×(n+1) — matrices are 1-indexed here.
- Deep recursion in Python (depth ~n) plus overhead makes tabulation preferable for large chains.
Approach 3 of 3 · Optimal
Bottom-Up — Interval DP by Increasing Length (Optimal)
1Hint 1Explore hintHide hint
The cost of interval [i, j] needs the costs of strictly shorter intervals [i, k] and [k+1, j]. So solve all length-1 intervals, then length-2, ... up to length-n.
2Hint 2Explore hintHide hint
dp[i][i] = 0. For length L from 2 to n, set i from 1, j = i + L - 1, and try every split k in i..j-1.
3Hint 3Explore hintHide hint
dp[i][j] = min over k of dp[i][k] + dp[k+1][j] + p[i-1]·p[k]·p[j]. The answer is dp[1][n].
A · Core idea
Build the table by increasing interval length so every sub-interval is finalized before it's needed. Set the diagonal dp[i][i] = 0. Then for each length L from 2 to n, walk the left endpoint i, compute the right endpoint j = i + L - 1, and try every outermost split k in i..j-1, relaxing dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + p[i-1]·p[k]·p[j]). The answer is dp[1][n].
The mental shift: length is the dependency order. Interval [i, j] of length L depends only on intervals [i, k] and [k+1, j], both strictly shorter than L. So if we fill by increasing length, both pieces are always already computed when we reach the merge — no recursion needed, just three nested loops (length, left endpoint, split point). This length-ordered fill is the defining move of interval DP; plain row-major i, j iteration would read cells that aren't ready yet.
Re-deriving the merge cost in table terms. When we combine [i, k] (a matrix of shape p[i-1] × p[k]) with [k+1, j] (shape p[k] × p[j]), the multiplication costs p[i-1] · p[k] · p[j] and produces the p[i-1] × p[j] matrix that interval [i, j] represents. Add that to the two cached sub-costs.
Why the diagonal is the base. A length-1 interval is a single matrix — zero multiplications. Every larger interval's cost is anchored on these zeros, the same way dp[0] anchors a linear DP.
Why min over all k. Each split is a different bracketing of the same product; we keep the cheapest.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
p = [10, 20, 30, 40] (3 matrices)Interactive diagram
Upper-triangular dp table filled by length
L=1dp[i][j] for p=[10,20,30,40]. Diagonal is 0; fill direction goes up-right by increasing length. Answer at dp[1][3].
18000C · Code with teaching comments
D · Why it works and complexityO(n³) timeO(n²) spaceOpen the invariant and proofExplore the proofHide the proof
This is the canonical interval-DP template: state = contiguous range, decision = the outermost split k, fill order = increasing length. Swap the cost function and you've solved Burst Balloons (split on the LAST balloon to pop), Palindrome Partitioning II (split into palindromic pieces), and Boolean Parenthesization (split a boolean expression). Learn the skeleton once, reuse it everywhere.
ComplexityO(n³) time, O(n²) space — There are O(n²) intervals; each scans up to O(n) split points → O(n³) time. The dp table is (n+1)² → O(n²) space, and there's no recursion stack.
E · Edge cases and pitfalls6n = 1 (single matrix) — Length loop never runs; dp[1][1] = 0 returned.Explore edge casesHide edge cases
Edge cases handled
n = 1 (single matrix)Length loop never runs; dp[1][1] = 0 returned.n = 2Only L=2, single split k=1: dp[1][2] = p[0]·p[1]·p[2].all dimensions equal (d)Every merge costs d³ and any bracketing ties — DP returns (n-1)·d³.
Pitfalls
- Iterating i, j in plain order instead of by length — reads dp[i][k] / dp[k+1][j] before they're computed.
- Forgetting to reset dp[i][j] to +∞ before the split loop — leaves a stale 0 that wins the min.
- Off-by-one in the merge triple — it must be p[i-1]·p[k]·p[j], not p[i]·p[k]·p[j].
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int matrixChain(int[] p) { int n = p.length - 1; int[][] dp = new int[n + 1][n + 1]; for (int len = 2; len <= n; len++) { for (int i = 1; i + len - 1 <= n; i++) {Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Wrong table fill order
dp[i][j] reads dp[i][k] and dp[k+1][j], which are SHORTER intervals. Iterating i ascending and j ascending visits dp[i][j] before some shorter intervals are done, reading stale zeros. Fill by increasing length.
Explore the code comparisonHide the code comparison
Wrong table fill order
dp[i][j] reads dp[i][k] and dp[k+1][j], which are SHORTER intervals. Iterating i ascending and j ascending visits dp[i][j] before some shorter intervals are done, reading stale zeros. Fill by increasing length.
Don't write this
for i in range(1, n + 1):
for j in range(i + 1, n + 1): # length not controlled
dp[i][j] = float('inf')
for k in range(i, j):
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j])Write this instead
for length in range(2, n + 1):
for i in range(1, n - length + 2):
j = i + length - 1
dp[i][j] = float('inf')
for k in range(i, j):
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j])2Wrong merge-cost triple
Combining [i,k] (shape p[i-1]×p[k]) with [k+1,j] (shape p[k]×p[j]) costs p[i-1]·p[k]·p[j]. Using p[i]·p[k]·p[j] silently computes a different, wrong cost.
Explore the code comparisonHide the code comparison
Wrong merge-cost triple
Combining [i,k] (shape p[i-1]×p[k]) with [k+1,j] (shape p[k]×p[j]) costs p[i-1]·p[k]·p[j]. Using p[i]·p[k]·p[j] silently computes a different, wrong cost.
Don't write this
int cost = dp[i][k] + dp[k + 1][j] + p[i] * p[k] * p[j];Write this instead
int cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j];3Not resetting the interval cost before the split loop
If dp[i][j] still holds its initialized 0, the min over splits never improves past 0 and the answer collapses to 0. Set it to +∞ first.
Explore the code comparisonHide the code comparison
Not resetting the interval cost before the split loop
If dp[i][j] still holds its initialized 0, the min over splits never improves past 0 and the answer collapses to 0. Set it to +∞ first.
Don't write this
for (int k = i; k < j; k++) {
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]); // dp[i][j] starts at 0
}Write this instead
dp[i][j] = Integer.MAX_VALUE;
for (int k = i; k < j; k++) {
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]);
}Revise
Carry the pattern into the interview
Pattern to remember
Interval DP — split a chain at every cut point
Code pattern to memorize
dp[i][i] = 0
for length L in 2..n:
for i in 1..n-L+1:
j = i + L - 1
dp[i][j] = min over k in i..j-1 of
dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]
return dp[1][n]Rules to remember
- 1You're choosing where to put the last multiplication (the outermost split
k), not the first — the two halvesi..kandk+1..jare solved independently. - 2The merge cost of joining the two halves is
p[i-1] · p[k] · p[j]: the left result isp[i-1] × p[k], the right isp[k] × p[j], multiplying them costs that product. - 3It's an interval DP: state is a contiguous range
[i, j], and you must fill by increasing length so both sub-intervals are ready before the merge. - 4
dp[i][i] = 0— a single matrix needs no multiplication. The diagonal is the base case. - 5Dimensions array has
n+1entries fornmatrices; matrixiisp[i-1] × p[i]. Off-by-one here is the classic trap.
Use this pattern when
- Optimize over all ways to parenthesize / bracket a sequence
- Cost of combining two adjacent groups depends on a boundary value between them
- State is a contiguous interval [i, j] and the answer combines two sub-intervals
- Splitting at a middle point k decouples the problem into independent left/right halves
Choose another pattern when
- Each element decided independently (take/skip) → knapsack-style linear DP, not interval
- Cost of merging doesn't depend on a shared boundary → probably a simpler 1-D DP
- You need the actual parenthesization, not just the cost → store a split table alongside dp
- n is large (thousands) → O(n³) may be too slow; look for special structure (Hu–Shing for matrices)
Interview takeaway
Matrix Chain is the gateway interval DP. The move that unlocks it: don't pick the first multiplication, pick the LAST one — the outermost split k cleanly separates [i..k] and [k+1..j]. Fill by increasing interval length so sub-intervals are ready. The same 'split at every k, fill by length' template solves Burst Balloons, Palindrome Partitioning II, and Boolean Parenthesization.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical interval DP. Recognize it whenever the state is a contiguous range [i, j] and the answer is built by choosing an outermost split point k that separates two independent sub-intervals, with a boundary-dependent merge cost. Fill by increasing length. Same template as Burst Balloons, Palindrome Partitioning II, and polygon triangulation.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Burst BalloonsComing soonInterval DP where you split on the LAST balloon to burst in (i, j) — same template, different merge cost.
- Palindrome Partitioning IIComing soonMin cuts to split a string into palindromes — interval reasoning over substrings.
- Minimum Score Triangulation of PolygonComing soonTriangulate a polygon at minimum cost — split on the third vertex of a triangle, identical interval-DP shape.
- Boolean ParenthesizationCount parenthesizations of a boolean expression that evaluate true — split on each operator, an interval DP.