Matrix Chain Multiplication
AlgorithmsHardCompute optimal parenthesizations to minimize scalar multiplications.
Alt+Shift+M
Configuration Panel
MCM Cost Grid (dp[i][j])
DP table is empty.
Time Complexity
O(N^3)
Space Complexity
O(N^2) state space size
Conceptual Overview
The Matrix Chain Multiplication (MCM) problem determines the most efficient way to multiply a given sequence of matrices, finding an order that minimizes the total scalar multiplications.
Recurrence Relation
dp[i][j] = min(dp[i][k] + dp[k+1][j] + P[i-1]*P[k]*P[j]) for all k in [i, j-1]
State Transitions
Splits the matrix chain into two sub-chains: matrices i..k and matrices k+1..j, summing subproblem costs plus the cost to multiply the two resulting matrices.
Source: CP-Algorithms dynamic programming reference