Matrix Chain Order Interview Questions: Worked DP Answers
Build Matrix Chain Order from the multiplication rule to the recurrence, then trace every split for four matrices and reconstruct the optimal answer.
KnowledgeGate Team
Exam prep & CS education

Memorising the cubic recurrence is easy; explaining m[i][j], changing dimensions, and split-table reconstruction is harder. Many candidates can quote the formula but cannot justify it when a follow-up goes deeper. For [40,20,30,10,30], the minimum cost 26000, the optimal parenthesisation ((A1(A2A3))A4), complexity, and follow-ups. The same topic appears in the Dynamic Programming lesson of the DSA course.
What exactly does Matrix Chain Order optimise?
Model answer: Matrix Chain Order, or Matrix Chain Multiplication, finds the least-cost parenthesisation of a fixed compatible sequence. Valid parenthesisations give the same result, but scalar costs can differ. It neither reorders matrices nor calculates entries.
Multiplying p x q by q x r costs p*q*r scalar multiplications and produces p x r. Thus A1(40x20) * A2(20x30) costs 40*20*30 = 24000 and produces 40x30. A2 * A1 is incompatible because 30 != 40, and is forbidden because it changes the order.
For p=[40,20,30,10,30], Ai has shape p[i-1] x p[i]. Thus A1=40x20, A2=20x30, A3=30x10, and A4=10x30. For a refresher on states and transitions, see Dynamic Programming Explained with a Worked 0/1 Knapsack.
Why does parenthesisation matter?
Four matrices have Catalan C3 = 5 full parenthesisations. Their complete costs are:
(((A1A2)A3)A4) = 24000 + 12000 + 12000 = 48000((A1(A2A3))A4) = 6000 + 8000 + 12000 = 26000((A1A2)(A3A4)) = 24000 + 9000 + 36000 = 69000(A1((A2A3)A4)) = 6000 + 6000 + 24000 = 36000(A1(A2(A3A4))) = 9000 + 18000 + 24000 = 51000
In the winning plan, A2A3 produces 20x10, A1(A2A3) produces 40x10, and multiplying by A4 produces the final 40x30 matrix. The minimum is 26000. The value 14000 covers only the first three matrices in that plan.
Exhaustive search follows Catalan growth, so listing every tree soon becomes impractical. Choosing the currently cheapest adjacent pair is not a general proof of optimality either, because every merge changes the dimensions used by later multiplications.

How do you derive the DP recurrence?
Let m[i][j] be the minimum scalar multiplications for the fixed subchain Ai...Aj. Set m[i][i]=0 because one matrix needs no multiplication. Let s[i][j] store the best split k, choosing the smallest k to break a tie deterministically.
For a split after Ak, solve Ai...Ak and A(k+1)...Aj. Their results have shapes p[i-1] x p[k] and p[k] x p[j], so the combine cost is p[i-1]*p[k]*p[j]. Therefore:
m[i][j] = min over k=i..j-1 {m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]}
An interval of length L reads shorter intervals, so tabulation fills lengths 2,3,...,n. Memoisation uses the same state and recurrence.
Can you fill the complete cost and split tables?
For length 2:
m[1,2]=40*20*30=24000, sos[1,2]=1m[2,3]=20*30*10=6000, sos[2,3]=2m[3,4]=30*10*30=9000, sos[3,4]=3
For length 3, m[1,3] has two candidates. At k=1, the cost is 0+6000+40*20*10=14000. At k=2, it is 24000+0+40*30*10=36000. Store m[1,3]=14000 and s[1,3]=1. For m[2,4], k=2 gives 0+9000+20*30*30=27000, while k=3 gives 6000+0+20*10*30=12000. Store m[2,4]=12000 and s[2,4]=3.
For length 4, the candidates for m[1,4] are 0+12000+40*20*30=36000 at k=1, 24000+9000+40*30*30=69000 at k=2, and 14000+0+40*10*30=26000 at k=3. Hence m[1,4]=26000 and s[1,4]=3.
| 1 | 2 | 3 | 4 |
|---|---|---|---|---|
1 | 0 | 24000 | 14000 | 26000 |
2 | - | 0 | 6000 | 12000 |
3 | - | - | 0 | 9000 |
4 | - | - | - | 0 |
| 1 | 2 | 3 | 4 |
|---|---|---|---|---|
1 | - | 1 | 1 | 3 |
2 | - | - | 2 | 3 |
3 | - | - | - | 3 |
4 | - | - | - | - |
![Upper-triangular Matrix Chain Order cost and split tables for p=[40,20,30,10,30], with fill lengths and optimal m[1,4]=26000, s[1,4]=3 highlighted.](https://cdn.knowledgegate.ai/blog-assets/blog_asset_1786687771227_q2aan2.jpg)
How do you reconstruct the answer and discuss implementation?
Backtrack through s. First, s[1,4]=3 gives (A1...A3)A4. Then s[1,3]=1 gives A1(A2...A3), and s[2,3]=2 gives A2A3. The final string is ((A1(A2A3))A4). Its costs check out as 6000 + 8000 + 12000 = 26000.
for i = 1 to n:
m[i][i] = 0
for length = 2 to n:
for i = 1 to n - length + 1:
j = i + length - 1
m[i][j] = infinity
for k = i to j - 1:
q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]
if q < m[i][j]:
m[i][j] = q
s[i][j] = k
return m[1][n], reconstruct(s, 1, n)With n matrices, p has n+1 entries. Zero-based implementations must rewrite every index consistently. Use a numeric type wide enough for dimension products and accumulated costs.
What are the time, space and implementation follow-ups?
There are O(n^2) intervals and up to O(n) splits per interval, so time is O(n^3). The two tables use O(n^2) space. Here the algorithm evaluates exactly 3+4+3=10 candidates: three length-2 cells with one split each, two length-3 cells with two each, and one length-4 cell with three.
Memoisation recursively explores and caches the same intervals. Tabulation makes length order explicit and avoids recursion-stack overhead. Both have the same worst-case time and table space when all intervals are needed.
A rolling array does not preserve this interval dependency pattern. Reconstruction also needs stored splits, so do not promise O(n) space while returning the full structure.
Which traps and edge cases should a model answer catch?
Trap | What goes wrong | Repair |
|---|---|---|
Reordering matrices | Solves a different or invalid chain | Preserve |
Counting matrix multiplications | Every plan has | Count scalar multiplications |
Forgetting subproblem costs | Chooses only a cheap final merge | Add left, right and combine costs |
Wrong dimensions | Uses | Use |
Storing cost but no split | Cannot reconstruct parentheses | Maintain |
32-bit overflow | A candidate wraps or becomes negative | Use a wide integer and safe infinity |
Boundary tests: p=[10,20] means one matrix, cost 0, answer A1. For p=[10,20,30], the cost is 10*20*30=6000, answer (A1A2). For [10,20,30,40], ((A1A2)A3) costs 6000+12000=18000, while (A1(A2A3)) costs 24000+8000=32000.
Dimensions must be positive and p needs at least two entries. Consecutive entries ensure compatibility.
How should you answer this topic in an interview?
Foundation prompts test the two-matrix rule or compare parenthesisations. Derivation prompts cover state, recurrence, and fill order. Dry runs ask for one cell; follow-ups cover reconstruction, complexity, overflow, memoisation, and edge cases. DSA Interview Questions: 7 Patterns for Placements gives a broader structure.
The 45-second answer: m[i][j] is the cheapest cost for Ai...Aj. Try every k, add both subproblem costs and p[i-1]*p[k]*p[j], fill shorter intervals first, and save k to reconstruct. The result is O(n^3) time and O(n^2) space. Checksum: p=[40,20,30,10,30] -> 26000 -> ((A1(A2A3))A4).
Continue with DSA using Java for implementation practice, or Coding for Placements for broader coding-round preparation.
Keep learning
Matrix Chain Order: DP Recurrence, Table and a 4-Matrix Worked Example
See why order changes scalar cost even when the final matrix does not. Build both DP tables for p = [5, 10, 3, 12, 5] and recover the 405-cost solution.
Matrix Chain Order MCQs: 12 Solved GATE and UGC NET Questions with Explanations
Solve Matrix Chain Multiplication questions by applying one cost rule, comparing valid groupings, and filling the dynamic-programming table without arithmetic slips.
Dynamic Programming Interview Questions: 10 Worked Answers for Beginners
Build interview-ready DP reasoning through ten beginner questions, exact traces, language-neutral pseudocode and clear complexity analysis.
Advanced DP Interview Questions and Answers: Four Worked Patterns
Work through four advanced dynamic programming patterns with exact states, transitions, reconstructions, proof hooks, and interview-ready explanations.





