Dynamic programming and Matrix Chain Order

Algorithms · Optimization

Dynamic programming and Matrix Chain Order

Dynamic programming solves each subproblem once and stores the result. Matrix Chain Order makes the method especially visible: the optimal cost emerges by filling two triangular tables one diagonal at a time.

When a problem fits dynamic programming

Splitting a problem is not enough. Dynamic programming helps when many recursive paths ask for the same subproblems and a globally optimal solution can be assembled from optimal smaller solutions.

Optimal substructure

An optimal choice contains optimal choices for the subproblems it creates.

Overlapping subproblems

Naive recursion recomputes the same states. Storing them removes that repetition.

State and choice

Define exactly what a cell represents and which decision reduces it to smaller states.

It is not one algorithm. It is a design method: define states, a recurrence, base cases, evaluation order and, when needed, how to reconstruct the choices.

Two ways to evaluate the same states

Top-down

Memoization

Start from the full problem, recurse and cache each result on first visit. Only requested states are evaluated.

Bottom-up

Tabulation

Start from base cases and fill a table in an order that makes every dependency available. MatrixChainOrder uses this approach.

The problem: where should parentheses go?

Matrix multiplication is associative, so every parenthesization produces the same final matrix. The number of scalar multiplications can change dramatically. We are not multiplying the matrices: we are choosing the least expensive order.

(A₁A₂)A₃

10·30·5 + 10·5·60 = 4 500

A₁(A₂A₃)

30·5·60 + 10·30·60 = 27 000

A chain of n matrices is described by the vector p[0…n]: Aᵢ has dimensions p[i−1] × p[i].

State, base case and recurrence

m[i,j] is the minimum number of scalar multiplications needed to compute Aᵢ…Aⱼ. s[i,j] stores the value of k that achieves that minimum.

m [i, i] = 0

Chains of length 1 cost zero. For a longer chain, try every last split k: the left cost, the right cost and the cost of multiplying the two results.

Lab: fill the rotated tables

As in the board diagram, the base-case diagonal sits at the bottom. Each new diagonal moves up one level: when a cell is evaluated, every cell it depends on is already filled.

Mminimum costs m[i,j]

Soptimal splits s[i,j]

Speed 1×

Current calculation m[i,j]

Play the animation to compare splits.

Length ℓ: 1
Cell: —
Split k: —
Comparisons: 0

Synchronized pseudocode

for i ← 1 to n: m[i,i] ← 0
for ℓ ← 2 to n
for i ← 1 to n − ℓ + 1
j ← i + ℓ − 1
m[i,j] ← ∞
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

Current solution

—

Optimal cost: —

target cell used subproblems new minimum completed cell

Table S reconstructs the parentheses

M stores the optimal value but not the choices that produced it. S stores each split: starting from s[1,n], recursively reconstruct A₁…Aₖ and then Aₖ₊₁…Aₙ.

Print(i,j) \to if i = j print Aᵢ; otherwise print “(”, Print(i,s[i,j]), Print(s[i,j]+1,j), “)”.

General pattern. When you need the solution rather than only its value, store the best decision alongside each state value.

Correctness and complexity analysis

When evaluating m[i,j], every parenthesization has one final multiplication splitting the chain into Aᵢ…Aₖ and Aₖ₊₁…Aⱼ for a unique k. By optimal substructure, if either side were not optimal, replacing it would improve the global solution. Trying every k and taking the minimum is therefore sufficient.

Resource	Cost	Why
Subproblems	Θ(n²)	One cell for each interval [i,j].
Time	Θ(n³)	Up to n−1 splits are tried for each interval.
Space	Θ(n²)	The two triangular tables M and S.
Reconstruction	Θ(n)	The parenthesization contains n matrices and n−1 splits.

Common mistakes

Confusing the number n of matrices with the n+1 length of vector p.
Using p[i], p[k] and p[j] instead of p[i−1], p[k] and p[j] for the final multiplication cost.
Filling by rows: m[i,j] depends on shorter intervals, so increasing chain length is the safe order.
Storing the cost in S: S contains index k, not value q.
Assuming the algorithm performs multiplication: it only computes the optimal order.

Exercises to consolidate the method

Try p = [10, 20, 30, 40]. Before playing, manually compute the two candidates for m[1,3].
In the lesson example, locate the cells used to evaluate m[2,5] when k = 3.
Find a four-matrix chain where left-to-right parenthesization is optimal, and one where it is worst.
Conceptually modify the algorithm to count how many parenthesizations achieve the same minimum cost.