Matrix Chain Multiplication

Given matrices $A_1\times A_2\times \cdots \times A_n$ with dimensions $p_0\times p_1$, $p_1\times p_2$, …, $p_{n-1}\times p_n$, find the parenthesisation minimising the number of scalar multiplications.

Multiplying a $p\times q$ by a $q\times r$ matrix costs $p\cdot q\cdot r$. Matrix multiplication is associative, so the result never changes — only the cost.

Why the order matters

For dimensions $10\times 100$, $100\times 5$, $5\times 50$:

• $((A_1{A}_2)A_3)$: $10\cdot 100\cdot 5+10\cdot 5\cdot 50=5000+2500=7500$
• $(A_1(A_2{A}_3))$: $100\cdot 5\cdot 50+10\cdot 100\cdot 50=25000+50000=75000$

A 10× difference from parenthesisation alone.

The recurrence

$dp[i][j]={\min }_{i<k<j}(dp[i][k]+dp[k][j]+p_i{p}_k{p}_j),dp[i][i+1]=0.$

Here $dp[i][j]$ is the cost of multiplying the matrices spanning dimension indices $i$ to $j$.

long long matrixChain(vector<long long>& p) {
    int n = p.size() - 1;                            // number of matrices
    vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, 0));
    for (int len = 2; len <= n; len++)               // by increasing length
        for (int i = 0; i + len <= n; i++) {
            int j = i + len;
            dp[i][j] = LLONG_MAX;
            for (int k = i + 1; k < j; k++)
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + p[i]*p[k]*p[j]);
        }
    return dp[0][n];
}

$O(n^3)$ time, $O(n^2)$ space. Iterating by length is essential — see Interval DP.

Reconstructing the parenthesisation

vector<vector<int>> split;                          // split[i][j] = best k
string build(int i, int j) {
    if (j == i + 1) return "A" + to_string(i + 1);
    return "(" + build(i, split[i][j]) + " x " + build(split[i][j], j) + ")";
}

Can it be optimised?

Knuth optimization does not apply

The cost $p_i{p}_k{p}_j$ does not satisfy the quadrangle inequality in general, so Knuth optimization is invalid here and matrix chain stays $O(n^3)$ for the general DP. This is a common misconception — Knuth’s own $O(n^2)$ result was for optimal binary search trees, whose cost function is Monge.

There is a specialised $O(n\log n)$ algorithm (Hu-Shing, 1982) that exploits the geometric structure of the problem, but it is intricate and essentially never needed: $n$ in contest versions of this problem is small.

The interval-DP family it belongs to

Problem	Cost of merging $[i,k]$ and $[k,j]$
Matrix chain	$p_i{p}_k{p}_j$
Merging stones	sum of the range
Optimal BST	sum of the frequencies in the range
Polygon triangulation	area or perimeter of the triangle $(i,k,j)$
Huffman (free order)	greedy, $O(n\log n)$
Hu-Tucker (fixed order)	$O(n\log n)$

Note the last two rows: when the leaves may be reordered, greedy Huffman solves it in $O(n\log n)$; when the order is fixed, you need Hu-Tucker or an $O(n^2)$ Knuth-optimised DP. Matrix chain has a fixed order and a non-Monge cost, which is why it is the hard case.

Polygon triangulation — the same DP

Triangulating a convex polygon to minimise the total triangle weight is exactly this recurrence with $\mathrm{cost}(i,k,j)$ being the weight of triangle $(i,k,j)$. The dimension array $p$ corresponds to the polygon’s vertices, and each parenthesisation corresponds to a triangulation — a pleasing bijection, and the reason the number of parenthesisations is the Catalan number $C_{n-1}$.

Where it actually appears

• Optimising a chain of matrix multiplications in a linear algebra pipeline
• Query planning in databases (join order optimisation is the same shape)
• Tensor contraction ordering in machine learning frameworks
• As the standard teaching example of interval DP

See also: Interval DP · Knuth Optimization · Catalan Numbers