Matrix Chain Multiplication

You probably learned matrix multiplication in school: multiply the rows of one matrix against the columns of the next. If A is 10×30 and B is 30×5, computing A·B costs 10 × 30 × 5 = 1,500 multiplications.

Now suppose you have a chain of matrices: A·B·C. Matrix multiplication is associative — (A·B)·C gives exactly the same answer as A·(B·C). The math is the same; the work is not. Depending on the dimensions, one parenthesization can cost thousands of times more than the other.

With just three matrices the choice is obvious. But with ten matrices there are 4,862 different parenthesizations to consider, and with twenty there are over six billion. Brute force is hopeless.

This is where dynamic programming earns its keep. By breaking the problem into overlapping subproblems and storing partial results, it finds the cheapest multiplication order for any chain of n matrices in $O(n^{3})$ time — an enormous speedup over exponential brute force. The algorithm was first described by Godbole (1973) and independently by Yao (1975) and is now a cornerstone example of dynamic programming alongside sequence alignment and coin change.

Set the dimensions of four matrices using the sliders below. Each slider sets one dimension — the chain is A($d_{0}$×$d_{1}$) · B($d_{1}$×$d_{2}$) · C($d_{2}$×$d_{3}$) · D($d_{3}$×$d_{4}$).

<div class="controls" id="controls">
  <div class="dim-row" id="dim-row"></div>
</div>
<div class="chain-label" id="chain-label"></div>
<div class="table-wrap">
  <table id="dp-table"></table>
</div>
<div class="result" id="result"></div>
<div class="paren" id="paren"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; font-size: 14px; }
.controls { margin-bottom: .6rem; }
.dim-row { display: flex; gap: 1.2rem; flex-wrap: wrap; align-items: flex-end; }
.slider-group { display: flex; flex-direction: column; align-items: center; gap: .2rem; }
.slider-group label { font-size: .75rem; color: #555; font-weight: 600; }
.slider-group span { font-size: .9rem; font-weight: 700; color: #1d3557; min-width: 2ch; text-align: center; }
input[type=range] { width: 70px; accent-color: #1d3557; }
.chain-label { font-size: .85rem; color: #444; margin-bottom: .5rem; }
.chain-label b { color: #1d3557; }
.table-wrap { overflow-x: auto; margin-bottom: .6rem; }
table { border-collapse: collapse; }
td { width: 56px; height: 38px; text-align: center; vertical-align: middle;
     border: 1px solid #cdd9e3; font-size: .8rem; }
td.header { background: #e8eef3; font-weight: 700; color: #1d3557; font-size: .75rem; }
td.empty { background: #f5f7fa; }
td.zero { background: #edf4ff; color: #1d3557; font-weight: 600; }
td.filled { background: #fff; color: #222; }
td.optimal { background: #d4edda; color: #155724; font-weight: 700; }
td.best { background: #1d3557; color: #fff; font-weight: 700; }
.result { font-weight: 700; color: #1d3557; font-size: 1rem; margin-bottom: .3rem; min-height: 1.4em; }
.paren { font-size: .85rem; color: #444; }
.paren b { color: #1d3557; }

// Code not found

The DP table shows the minimum cost (in scalar multiplications) to multiply each consecutive sub-chain. The cell at row i, column j holds the cheapest way to compute the product of matrices i through j. The bottom-right corner is the answer for the full chain. The highlighted split point shows where to place the outermost parentheses for optimal cost.

Why is the brute-force search so expensive, and how does dynamic programming fix it?

Counting the parenthesizations. The number of ways to fully parenthesize a chain of n matrices is the (n−1)th Catalan number. These grow roughly as $4^{n}$ / $n^{3/2}$ — faster than any polynomial. For n = 20 that is already more than six billion.

Why brute force fails. To evaluate every parenthesization you would need to evaluate every sub-chain many times over. The key insight is that those sub-chain evaluations overlap: the cost of multiplying matrices 2 through 5 is the same regardless of what surrounds them. Brute force recomputes each one from scratch; this is pure waste.

Dynamic programming's fix. Build a table dp[i][j] = the minimum cost to multiply matrices i through j. Fill it bottom-up: start with chains of length 1 (cost 0), then length 2, 3, and so on up to the full chain. Each entry requires trying all possible split points k between i and j:

dp[i][j] = min over k of (dp[i][k] + dp[k+1][j] + d[i] × d[k+1] × d[j+1])

There are $O(n^{2})$ entries and each takes $O(n)$ to fill, giving $O(n^{3})$ total — a dramatic collapse from exponential.

Status: Solved. The $O(n^{3})$ algorithm is optimal in the comparison model. Hu and Shing (1982) later found an $O(n \log n)$ algorithm for the special case where all matrices are square, but the general $O(n^{3})$ DP remains the standard solution. This is a solved problem in P, a textbook example of how the right structure transforms an intractable search into an efficient computation — unlike P vs NP problems where no such structure is known.

Matrix chain multiplication is not a textbook toy — it shows up wherever large chains of linear transformations are computed:

• Deep learning: a neural network's forward pass is a long chain of matrix multiplications (weight matrices times activations). Frameworks like TensorFlow and PyTorch use operator fusion and expression optimization that draws on exactly this idea to minimize computation.
• Computer graphics: 3D transformations — model, view, and projection matrices — are composed before being applied to millions of vertices. Choosing the right grouping can reduce GPU load substantially.
• Compiler expression optimization: compilers that handle array or tensor expressions (e.g., BLAS wrappers, Julia, NumPy einsum) apply chain-multiplication analysis to rewrite expressions into the cheapest equivalent form.
• Scientific computing: quantum chemistry and physics simulations multiply long chains of operators; the cost difference between bad and optimal ordering can be the difference between a feasible and an infeasible computation.
• Teaching dynamic programming: the matrix-chain problem is a canonical example taught in algorithms courses worldwide precisely because it illustrates all three DP principles — overlapping subproblems, optimal substructure, and memoization — in a concrete, measurable setting.

The same idea generalizes to optimal binary search trees, polygon triangulation, and any problem where you must choose how to split a sequence and the cost depends on both sides.

Matrix chain multiplication is one of computer science's cleanest stories: a question that looks routine — just multiply some matrices — turns out to hide an exponential search space, and then dynamic programming dissolves that complexity entirely with a single elegant table-fill.

The algorithm is solved and sits firmly in P. It is not a hard problem but a well-structured one — a reminder that difficulty is often about structure, not scale. Identify the overlapping subproblems, store the answers, and what seemed intractable becomes routine.

Whenever you encounter a chain of operations where the order of evaluation can be chosen freely, ask yourself: is there a matrix-chain insight hiding here? Chances are, there is — and dynamic programming is the key to finding it.