DP: Matrix Chain Multiplication

Multiplying a chain of matrices might seem like a straightforward task, but the order in which you perform the multiplications has a dramatic impact on computational cost. The Matrix Chain Multiplication (MCM) problem is a classic optimization challenge in computer science and engineering that asks: given a sequence of matrices, what parenthesization yields the minimum number of scalar multiplications? Mastering this problem is essential because it introduces a powerful dynamic programming (DP) pattern used in everything from compiler design to computational geometry.

The Problem and Why Order Matters

Matrix multiplication is associative, meaning $(A\times B)\times C=A\times (B\times C)$. However, these different parenthesizations are not computationally equivalent. The cost is determined by the dimensions of the matrices.

Consider three matrices: $A_{10\times 100}$, $B_{100\times 5}$, and $C_{5\times 50}$. The scalar multiplication count for two matrices, $X_{p\times q}$ and $Y_{q\times r}$, is $p\times q\times r$.

• Option 1: $(A\times B)\times C$
• Cost of $A\times B$: $10\times 100\times 5=5000$. Result is a $10\times 5$ matrix.
• Cost to multiply that result by $C$: $10\times 5\times 50=2500$.
• Total Cost: 7500.

• Option 2: $A\times (B\times C)$
• Cost of $B\times C$: $100\times 5\times 50=25000$. Result is a $100\times 50$ matrix.
• Cost to multiply $A$ by that result: $10\times 100\times 50=50000$.
• Total Cost: 75000.

As you can see, the first option is ten times more efficient. For a chain of $n$ matrices, the number of possible parenthesizations grows exponentially, making brute-force search infeasible. This is where dynamic programming provides an optimal $O(n^3)$ solution.

The Dynamic Programming Formulation

The core insight is to break the large problem—finding the optimal cost for the entire chain—into smaller, overlapping subproblems. We define a DP table m[i][j] which stores the minimum number of scalar multiplications needed to compute the product of matrices from index $i$ to index $j$ (inclusive).

We are given an array p[] of length $n+1$, where matrix $A_i$ has dimensions $p[i-1]\times p[i]$. For example, the earlier chain $A_{10\times 100},B_{100\times 5},C_{5\times 50}$ is represented as p = [10, 100, 5, 50].

The recurrence relation is the heart of the solution: $$m[i][j]=\{\begin{array}{ll}0& \text{if }i=j\text{ (single matrix, no multiplication)}\\ \underset{i\le k<j}{\min }\{m[i][k]+m[k+1][j]+p[i-1]\times p[k]\times p[j]\}& \text{if }i<j\end{array}$$

Let's decipher this. If we want the best way to multiply $A_i...A_j$, we consider all possible places $k$ to split the chain into two parts: $(A_i...A_k)$ and $(A_{k+1}...A_j)$. The cost is:

1. The cost to compute the left part: m[i][k]
2. The cost to compute the right part: m[k+1][j]
3. The cost to multiply the two resulting matrices together: $p[i-1]\times p[k]\times p[j]$.

We try every possible $k$ and choose the one that yields the minimum total cost.

The Bottom-Up Tabulation Approach

We solve this using a bottom-up DP approach to ensure subproblems are solved before they are needed. We fill the m[][] table in a specific order based on the chain length.

1. Initialization: Set m[i][i] = 0 for all $i$ (diagonal of the table).
2. Iteration: We compute the solution for chains of increasing length L, from 2 to $n$.

• For each chain length L, consider all possible starting points i.
• The ending point is j = i + L - 1.
• For each (i, j) pair, iterate through all possible split points k from i to j-1, apply the recurrence, and store the minimum cost in m[i][j]. We also store the optimal split point k in a separate table s[i][j] for later reconstruction.

This nested loop structure—over chain length, start index, and split point—results in the $O(n^3)$ time complexity. The space complexity is $O(n^2)$ for the tables.

Worked Example: For p = [10, 100, 5, 50] (3 matrices), after filling the table, m[1][3] would contain the answer 7500.

Reconstructing the Optimal Parenthesization

The m[][] table gives us the optimal cost, but not the order. This is where the auxiliary split table s[i][j] comes in. It stores the index $k$ at which we split the product $A_i...A_j$ for optimal parenthesization.

We reconstruct the solution using a recursive algorithm:

1. To print the parenthesization for $A_i...A_j$, if $i==j$, just print "A_i".
2. Otherwise, find the optimal split k = s[i][j].
3. Recursively print the parenthesization for the left part $(A_i...A_k)$ and the right part $(A_{k+1}...A_j)$, wrapping the entire expression in parentheses.

For our example, the reconstruction would yield the string "((A1 A2) A3)", corresponding to the optimal order we calculated manually.

Significance and Broader Applications

The Matrix Chain Multiplication problem is a paradigmatic interval DP problem. The pattern—defining a table over intervals [i, j] and partitioning the interval at all possible points k—is incredibly versatile.

This exact pattern translates directly to the problem of polygon triangulation, where the goal is to partition a convex polygon into triangles using non-intersecting diagonals while minimizing a cost function (e.g., sum of triangle perimeters). The vertices of the polygon are analogous to the matrices, and choosing a triangle (or split point $k$) creates two smaller sub-polygons to be solved recursively. Other applications include optimal binary search tree construction, string segmentation, and evaluating associative expressions in compilers.

Common Pitfalls

1. Incorrect Dimension Array Handling: The most common error is misindexing the dimension array p[]. Remember: if you have $n$ matrices, you need $n+1$ dimensions. Matrix $A_i$ is defined by p[i-1] and p[i]. Double-check your indices when computing the multiplication cost $p[i-1]\times p[k]\times p[j]$.

• Correction: Always verify with a small, hand-calculated example. For a chain starting at index 1, the cost of a split at k is always p[i-1]*p[k]*p[j].

1. Filling the DP Table in the Wrong Order: You cannot fill m[i][j] by simply iterating i and j from left to right. The value for m[i][j] depends on values for shorter intervals that are not yet computed in a simple row-major order.

• Correction: Always iterate by the chain length L from small to large, as described. This guarantees that m[i][k] and m[k+1][j] are already computed when you need them.

1. Confusing Cost with Reconstruction: Students often believe the DP table itself reveals the order. It only gives the minimum cost. Forgetting to build and use the split table s[][] leaves the solution incomplete.

• Correction: Always maintain the s[][] table simultaneously when computing the minimum in the inner k-loop. Record the k that gives the minimum m[i][j].

Summary

• The Matrix Chain Multiplication problem optimizes parenthesization to minimize scalar multiplications, with an efficient $O(n^3)$ dynamic programming solution replacing exponential brute-force search.
• The solution relies on a DP table m[i][j] for minimum cost of multiplying $A_i$ to $A_j$, and a split table s[i][j] to reconstruct the optimal order.
• The key recurrence tries all split points k: m[i][j] = min(m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]).
• The bottom-up tabulation must proceed by increasing chain length to satisfy dependencies between subproblems.
• This problem is the foundation for the interval DP pattern, with direct applications to problems like polygon triangulation, making it a fundamental algorithmic technique.