Introduction
Matrix multiplication is associative, meaning (A x B) x C equals A x (B x C), but the number of scalar multiplications required can differ dramatically depending on how you parenthesize the chain. The Matrix Chain Multiplication (MCM) problem asks: given a sequence of matrices with compatible dimensions, find the parenthesization (order of multiplication) that minimizes the total number of scalar multiplications. This is not about actually performing the multiplication, only about finding the optimal order. MCM is a foundational interval DP problem — it introduces the pattern of solving problems over subranges [i, j] of a sequence, which generalizes to many other 'optimal split point' problems.
Cricket analogy: Combining three partnership stands is associative in total runs regardless of grouping, but the order in which a captain sequences bowling changes across those stands can dramatically change the 'cost' in boundaries conceded, so finding the optimal sequencing (not the total) is the goal, mirroring MCM's focus on order over the actual product.
Approach/Syntax
def matrix_chain_order(dims):
"""dims: list where matrix i has dimensions dims[i-1] x dims[i], for i = 1..n"""
n = len(dims) - 1 # number of matrices
# dp[i][j] = minimum scalar multiplications to compute product of matrices i..j (1-indexed)
dp = [[0] * (n + 1) for _ in range(n + 1)]
split = [[0] * (n + 1) for _ in range(n + 1)]
for length in range(2, n + 1): # chain length from 2 to n
for i in range(1, n - length + 2):
j = i + length - 1
dp[i][j] = float('inf')
for k in range(i, j):
cost = dp[i][k] + dp[k + 1][j] + dims[i - 1] * dims[k] * dims[j]
if cost < dp[i][j]:
dp[i][j] = cost
split[i][j] = k
return dp, splitExplanation
We represent a chain of n matrices by a dimension array dims of length n+1, where matrix i has shape dims[i-1] x dims[i]. dp[i][j] holds the minimum number of scalar multiplications needed to compute the product of matrices i through j. The recurrence tries every possible split point k between i and j: multiply the subchain i..k first, then k+1..j, then combine the two resulting matrices, which costs dims[i-1] * dims[k] * dims[j] scalar multiplications (the dimensions of the two resulting matrices being multiplied together). We take the k that minimizes dp[i][k] + dp[k+1][j] + dims[i-1]*dims[k]*dims[j]. The base case dp[i][i] = 0 because a single matrix requires no multiplication. We fill the table by increasing chain length so that smaller subproblems are solved before larger ones depend on them. The split table records the optimal k for each (i, j), allowing reconstruction of the actual optimal parenthesization via a recursive print function.
Cricket analogy: Representing a tour by a dimensions array of squad sizes, dp[i][j] holds the minimum logistics cost to combine matches i through j; trying every split point k between them and taking the cheapest combination, with dp[i][i]=0 for a single match needing no combining, fills the table by increasing tour length.
Example
def matrix_chain_order(dims):
n = len(dims) - 1
dp = [[0] * (n + 1) for _ in range(n + 1)]
split = [[0] * (n + 1) for _ in range(n + 1)]
for length in range(2, n + 1):
for i in range(1, n - length + 2):
j = i + length - 1
dp[i][j] = float('inf')
for k in range(i, j):
cost = dp[i][k] + dp[k + 1][j] + dims[i - 1] * dims[k] * dims[j]
if cost < dp[i][j]:
dp[i][j] = cost
split[i][j] = k
return dp, split
def print_optimal_parens(split, i, j):
if i == j:
return f"A{i}"
k = split[i][j]
left = print_optimal_parens(split, i, k)
right = print_optimal_parens(split, k + 1, j)
return f"({left} x {right})"
if __name__ == "__main__":
# Matrices: A1 (10x30), A2 (30x5), A3 (5x60)
dims = [10, 30, 5, 60]
dp, split = matrix_chain_order(dims)
n = len(dims) - 1
print("Minimum scalar multiplications:", dp[1][n]) # 4500
print("Optimal order:", print_optimal_parens(split, 1, n)) # ((A1 x A2) x A3)Complexity
There are O(n^2) subproblems dp[i][j], and each is computed by trying up to O(n) split points k, giving overall time complexity O(n^3). Space complexity is O(n^2) for the dp and split tables. This is a textbook example of interval DP, where the state is a range [i, j] rather than a single prefix index, and the transition tries every internal split point — the same pattern reappears in problems like optimal binary search trees and palindrome partitioning.
Cricket analogy: With O(n^2) tour-segment combinations to evaluate and O(n) split points tried for each, total planning cost is O(n^3) time and O(n^2) space for the schedule table, the same interval-DP pattern used for optimal net-session bracketing.
Key Takeaways
- dp[i][j] = minimum scalar multiplications to multiply matrices i through j; base case dp[i][i] = 0.
- Recurrence tries every split point k: dp[i][j] = min over k of dp[i][k] + dp[k+1][j] + dims[i-1]*dims[k]*dims[j].
- Fill the table by increasing chain length so subproblems are solved before being reused.
- Overall time complexity is O(n^3); space complexity is O(n^2).
- This is the canonical example of interval DP, a pattern reused in many other range-based optimization problems.
Practice what you learned
1. What does dp[i][j] represent in the Matrix Chain Multiplication DP table?
2. What is the overall time complexity of the standard Matrix Chain Multiplication DP algorithm?
3. In the MCM recurrence, what does the term dims[i-1] * dims[k] * dims[j] represent?
4. Why must the DP table be filled in order of increasing chain length?
Was this page helpful?
You May Also Like
Introduction to Dynamic Programming
Learn what dynamic programming is and the two conditions — overlapping subproblems and optimal substructure — that make it applicable.
Longest Common Subsequence
Master the LCS DP recurrence for finding the longest shared subsequence between two strings in O(mn) time.
The Divide and Conquer Paradigm
Learn how divide, conquer, and combine steps break large problems into smaller solvable subproblems.