Problem Setup
Goal: Find the optimal way to parenthesize the matrix chain to minimize total scalar multiplications.
Key Insight: If we split at position k, cost = cost(i..k) + cost(k+1..j) + p[i-1]·p[k]·p[j]
Key Insight: If we split at position k, cost = cost(i..k) + cost(k+1..j) + p[i-1]·p[k]·p[j]
m[i,j] = min { m[i,k] + m[k+1,j] + pi-1·pk·pj }
i ≤ k < j
i ≤ k < j
DP Cost Table m[i,j]
Split Point Table s[i,j]
Current Cell
Comparing
Computed
Optimal Path