Back to Study Material Data Structures and Algorithms

Matrix Chain Multiplication

Matrix chain multiplication asks: given a sequence of matrices A1, A2, ..., An to be multiplied together, in what order should the multiplications be perfo...

Matrix Chain Multiplication

Problem Setup and Naive Complexity

Matrix chain multiplication asks: given a sequence of matrices A1, A2, ..., An to be multiplied together, in what order should the multiplications be performed to minimize the total number of scalar multiplications? Matrix multiplication is associative — the result is the same regardless of parenthesization — but the cost varies dramatically.

The cost of multiplying a p-by-q matrix and a q-by-r matrix is p*q*r scalar multiplications. For three matrices A (10x30), B (30x5), C (5x60), computing (AB)C costs 10*30*5 + 10*5*60 = 1500 + 3000 = 4500, while computing A(BC) costs 30*5*60 + 10*30*60 = 9000 + 18000 = 27000. The difference is a factor of six — a dramatic practical impact for large matrices.

The number of ways to parenthesize n matrices is the (n-1)-th Catalan number, which grows as O(4^n / n^(3/2)). Evaluating all parenthesizations by brute force is therefore exponential and completely impractical for even moderate n (say, n = 20).

The sub-problem structure: the outermost split in any parenthesization is a split between some matrix Ak and Ak+1 for 1 <= k < n. Once this split is chosen, the left product (A1...Ak) and right product (Ak+1...An) are independent sub-problems. Optimal substructure holds because an optimal parenthesization of the full chain must use optimal parenthesizations of both halves — otherwise you could replace a sub-optimal half with its optimal counterpart and reduce total cost.

Interview tip: State the problem using the p array of dimensions: matrix Ai has dimensions p[i-1] by p[i]. This compact representation (n+1 values for n matrices) avoids repeating the shared dimension and leads directly to the DP indexing.

Interval DP Recurrence and Fill Order

Define dp[i][j] as the minimum cost to multiply matrices Ai through Aj (1-indexed). Base cases: dp[i][i] = 0 for all i (a single matrix requires no multiplication). Recurrence: dp[i][j] = min over k from i to j-1 of (dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j]), where the third term is the cost of the final multiplication combining the left and right results.

The fill order is critical: dp[i][j] depends on dp[i][k] and dp[k+1][j], which are both sub-chains shorter than i..j. Therefore, fill by increasing chain length. For length l from 2 to n: for each starting index i from 1 to n-l+1: set j = i + l - 1, then compute dp[i][j] by trying all splits k.

A worked example with four matrices of dimensions 10x30, 30x5, 5x60, 60x10 (p = [10, 30, 5, 60, 10]). After filling by length, dp[1][4] gives the minimum multiplication cost for all four matrices. The DP table also records the optimal split point for reconstruction.

Time complexity: O(n^3) — three nested loops (chain length, start index, split point). Space complexity: O(n^2) for the dp table and the split table used for reconstruction. This is dramatically better than the exponential brute force.

To reconstruct the optimal parenthesization, maintain a separate table split[i][j] recording the k that minimized dp[i][j]. Recursively print the parenthesization: print_optimal(1, n) where print_optimal(i, j) recurses on print_optimal(i, split[i][j]) and print_optimal(split[i][j]+1, j).

Interview tip: The most common mistake in matrix chain multiplication is getting the indices wrong — off-by-one errors in the p array (which has n+1 elements for n matrices) or the loop bounds. Using 1-indexed matrices and explicitly writing p[i-1] by p[i] dimensions for matrix Ai makes the indexing clearer and reduces bugs.

Connections to Other Interval DP Problems

Matrix chain multiplication exemplifies interval DP, a pattern where the state is a sub-interval [i, j] of the input and the recurrence splits the interval at some internal point. Recognizing this pattern lets you reuse the same fill-order strategy for several other important problems.

Optimal binary search tree (OBST): given keys with access frequencies and optional dummy keys with gap frequencies, arrange them into a BST minimizing expected search time. State dp[i][j] = minimum expected cost for keys i through j; recurrence tries each key as the root and sums the sub-tree costs plus the incremented frequency of all keys (since they go one level deeper). Fill order: by chain length, exactly as in matrix chain.

Burst balloons (Leetcode 312): given balloons with values, bursting balloon i yields value left * i * right where left and right are its current neighbors. Find order that maximizes total value. This inverts the standard interval DP: the recurrence considers k as the last balloon burst in [i, j], giving dp[i][j] = max over k of (dp[i][k] + dp[k][j] + value[i] * value[k] * value[j]).

Minimum cost to cut a stick (Leetcode 1547): given cut positions, find the order of cuts that minimizes cost (cost of each cut equals current stick length). State dp[i][j] = minimum cost to perform all cuts strictly between positions i and j. Fill by length; recurrence tries each cut position as the first cut in [i, j].

All these problems share the interval DP skeleton: define dp[i][j], base case when i == j or interval has no elements, fill by increasing length, and try all splits inside the interval.

Interview tip: If a problem involves a sequence where the "last operation" on a sub-interval determines the cost and combines two independent sub-intervals, immediately try interval DP. Identifying the pattern quickly and naming it (interval DP, fill by length) is a strong signal of algorithmic breadth.