Matrix Chain Multiplication (Dynamic Programming)
Problem
- Given a sequence of matrices A1, A2, ..., An with dimensions p0 x p1, p1 x p2, ..., p(n-1) x pn, find the parenthesization that minimizes the total number of scalar multiplications.
Key idea (intuition)
- The order of multiplication affects cost (matrix multiplication is associative but not commutative). Use DP over chain lengths: cost for (i..j) depends on choosing a split k between i and j.
DP formulation
- Let
m[i][j]be the minimum cost (scalar multiplications) to compute the product A_i..A_j. For i == j,m[i][i] = 0. - For i < j:
m[i][j] = min_{i <= k < j} ( m[i][k] + m[k+1][j] + p_{i-1} * p_k * p_j ) - Keep a
s[i][j]table storing the split k that gives minimum cost to reconstruct optimal parenthesization.
Complexity
- Time: O(n^3) due to the triple loop (length, i, k).
- Space: O(n^2) for
mandstables.
Worked example
Dimensions: p = [10, 20, 30, 40] (three matrices: 10x20, 20x30, 30x40)
- Options:
- ((A1 A2) A3): cost = (102030) + (103040) = 600 + 12000 = 12600
- (A1 (A2 A3)): cost = (203040) + (102040) = 24000 + 8000 = 32000
- Best:
((A1 A2) A3)with cost 12600.
Reconstruction
- Use
s[i][j]to recursively print parenthesization.
Notes
- This DP is a classic example of optimal substructure + overlapping subproblems.
Code: main.cpp — fills m and s, prints minimum cost and optimal parenthesization.