Noesis
3.7.13 · D5Algorithm Paradigms

Question bank — DP problems — matrix chain multiplication

1,280 words6 min read↑ Back to topic
🇮🇳 Yeh page Hinglish mein padho →

True or false — justify

Matrix multiplication being associative means the cost is also the same for every parenthesization.
False. Associativity guarantees the same result matrix, but the number of scalar multiplications changes drastically (e.g. 7500 vs 75000) — that is exactly why MCM exists.
The contents (actual numbers) inside the matrices affect the optimal parenthesization.
False. Cost depends only on dimensions, so only the dimension array matters, never the entries.
For matrices the input dimension array has length .
False. It has length : matrix is , so matrices need boundaries .
is a definition we impose arbitrarily.
False. It follows from the problem: a single matrix requires zero multiplications because there is nothing to multiply it with.
Filling the DP table row by row (increasing ) gives the same answer, just in a different order.
False. depends on shorter chains and ; a row-major fill may read cells not yet computed. You must fill by increasing chain length .
MCM's recurrence has optimal substructure because the left and right sub-chains can be optimized independently once the split is fixed.
True. Fixing the last multiply at makes the two blocks independent problems, so combining their optimal costs is valid — this is precisely optimal substructure.
A top-down memoized version and the bottom-up table give different time complexities.
False. Both are : there are states each doing work. See Memoization vs Tabulation — order differs, asymptotics do not.
The split point ranges over .
False. It ranges . The left block is and the right is ; if the right block would be empty.

Spot the error

"The combine cost for splitting at is ."
Wrong index. The left block is and the right is , so the cost is — the left dimension is , not .
"Cost of multiplying an by a matrix is operations."
Wrong. Each of the output entries costs multiplications, giving . We count multiplications, not a sum of dimensions.
"We count both the additions and the multiplications, so cost is ."
The standard MCM cost counts only scalar multiplications (); additions are ignored by convention, so the extra term is not used.
"Greedy: always split at the smallest dimension , it's the cheapest join."
A locally cheap combine can force expensive sub-chains, making the total worse. Greedy provably fails (the 7500-vs-75000 case), so you must try every split — that's why it's DP not greedy.
" is found by the loop for i in 1..n: for j in i..n."
This visits states in the wrong dependency order. The correct outer loop is over chain length from 2 to ; only then are all shorter sub-chains ready.
"To reconstruct the answer we re-run the min over at query time."
Unnecessary and error-prone. We store the argmin in during the fill, then recurse on and using that table.
"Space is because there are three nested loops."
Loops give time . The stored tables and are 2D over , so space is . See Time Complexity Analysis.

Why questions

Why do we reason about the last multiplication rather than the first?
Every full parenthesization has exactly one outermost (final) multiply that splits the whole chain into two independent blocks. Fixing the last cut cleanly separates the problem; the first multiply does not partition the remaining structure the same way.
Why does plain recursion blow up while DP is polynomial?
The same sub-chains (like ) recur inside many parenthesizations — overlapping subproblems. Plain recursion re-solves them exponentially often; DP stores each once.
Why does the number of parenthesizations grow like a Catalan number?
Each parenthesization corresponds to a distinct binary tree of the leaves (matrices); the count of such trees is . See Catalan Numbers.
Why is MCM called an interval DP?
The state describes a contiguous interval of the chain, and transitions split that interval at an inner point. The same shape appears in Optimal Binary Search Tree and Burst Balloons.
Why can't we just memoize on a single index instead of a pair ?
A subproblem is a contiguous sub-chain, which needs both endpoints. One index cannot distinguish from .
Why do Burst Balloons fix the last balloon to burst while MCM fixes the last multiplication?
Both need the fixed element to make the two remaining sides independent. In MCM the split point separates left/right chains cleanly; in Burst Balloons only the last-burst balloon leaves independent sub-intervals.

Edge cases

What does MCM return for a single matrix (, )?
Zero. There is only ; the length loop for L in 2..n never runs, so no work is done.
For two matrices (), how many splits are tried and what is the cost?
Exactly one split (), giving cost . There is no choice, so "optimization" is trivial.
If two matrices in the chain are square and equal-sized, does parenthesization still matter?
It can still matter for the overall chain, but a run of identical matrices has every pairwise combine cost , so order among them alone is neutral — differences arise only via neighbouring non-equal dimensions.
Does a dimension of size (a row/column vector, e.g. ) change anything?
It's fully valid; it simply makes combines through that boundary cheap (), which often pulls the optimal split toward that . No special-casing needed.
Can ever be negative or benefit from an empty chain?
No. All dimensions are positive, so every combine cost is positive; costs only add up. There is no empty-chain case because the split enforces .
Is the optimal split point always unique?
No. Ties can occur where two splits give the same minimum cost. Any one is optimal; just records the one your comparison happened to keep.
Recall One-line self-test

Cover everything: (1) What is the combine cost formula? (2) What order fills the table? (3) Why not greedy? Combine cost ::: . Fill order ::: increasing chain length . Not greedy ::: a locally cheap split can force costly sub-chains; only trying all splits is safe.

Connections