Matrix Chain Multiplication

Matrix multiplication is associative but not commutative in cost — the order of multiplying a chain changes the total scalar operations dramatically. dp[i][j] tries every split point between i and j and keeps the cheapest.

Category

Dynamic Programming

Time complexity

O(n³)

Space complexity

O(n²)

Pseudocode

dp[i][i] = 0 (single matrix, free)
for increasing chain length
  dp[i][j] = min over split k of
    dp[i][k] + dp[k+1][j] + p[i-1]·p[k]·p[j]

Reference implementation

for length in range(2, n+1):
  for i in range(1, n-length+2):
    j = i + length - 1
    dp[i][j] = min(dp[i][k] + dp[k+1][j]
        + p[i-1]*p[k]*p[j] for k in range(i, j))

Open the interactive Matrix Chain Multiplication visualisation →