1. One-Liner
MCM minimizes total scalar multiplications to compute A1×…×An by splitting chains: dp[i][j] = optimal cost for matrices i..j.
2. The Problem It Solves
Matrix multiplication is associative but not commutative; different parenthesizations change operation count dramatically. You need the minimum cost schedule given dimensions p[0..n].
3. The Core Idea
Try every split k between i and j: cost = dp[i][k]+dp[k+1][j]+p[i-1]·p[k]·p[j]—optimal substructure on intervals.
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1 | dp[i][i]=0 |
| 2 | Increase length L from 2 to n |
| 3 | For each [i,j], try all k |
| 4 | Take minimum |
5. Dry Run Example
Dims [1,2,3,4] (three matrices)—compute costs for splits; optimal cost 18 for ((A1A2)A3) style evaluation (verify with standard example).
6. Key Properties
| Property | Value |
|---|---|
| Interval DP | Classic |
| Time | O(n³) |
7. Where It Is Used
| Domain | Use |
|---|---|
| Compilers | Expression reordering intuition |
| ML | Tensor contraction planning (advanced) |
8. Interview Tips
Print parenthesization via split table; contrast greedy failure cases.
9. Comparison with Other Algorithms
| Problem | Structure |
|---|---|
| MCM | Interval split |
| Optimal BST | Similar interval flavor |
10. Complexity
| Metric | Value |
|---|---|
| Time | O(n³) |
| Space | O(n²) |
Implementation Example (PYTHON)
def matrix_chain_order(p: list[int]) -> int:
n = len(p) - 1
dp = [[0] * n for _ in range(n)]
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = min(
dp[i][k] + dp[k + 1][j] + p[i] * p[k + 1] * p[j + 1] for k in range(i, j))
return dp[0][n - 1]