← Back

🧙 Matrix Mage

Optimal Matrix Chain Multiplication • Minimize scalar multiplications

Enter dimensions: A₁(d₀×d₁) × A₂(d₁×d₂) × ... means dimensions = d₀,d₁,d₂,...

📐 Matrices

📊 MCM DP Table (dp[i][j] = min cost to multiply Aᵢ...Aⱼ)

📐 MCM Formula

dp[i][j] = min cost for Aᵢ × ... × Aⱼ

dp[i][j] = min over all k:
  dp[i][k] + dp[k+1][j]
  + d[i-1] × d[k] × d[j]

Split at k: (Aᵢ...Aₖ) × (Aₖ₊₁...Aⱼ)
Matrices
-
Subproblems
-
Min Multiplications
?

💡 Why Order Matters

A(10×30) × B(30×5) × C(5×60)

(AB)C: 10×30×5 + 10×5×60 = 4500
A(BC): 30×5×60 + 10×30×60 = 27000

Same result, 6× difference!