Matrix Chain Multiplication

dp[i][j] = min over split k of dp[i][k] + dp[k+1][j] + dims[i-1]*dims[k]*dims[j]

time O(n^3)space O(n^2)

Matrix multiplication is associative, so (AB)C and A(BC) give the same result at very different costs — the shape of the parenthesization changes how many scalar multiplications happen. For a chain i..j, the LAST operation performed is always one split: multiply chain i..k, multiply chain k+1..j, then multiply those two results together. Try every split point k and keep the cheapest: dp[i][j] = min over k of dp[i][k] + dp[k+1][j] + dims[i-1]*dims[k]*dims[j], where the last term is the cost of that final multiplication. Filling the table by increasing chain length guarantees both halves of every split are already solved.

Details

Animated on: dims = [40,20,30,10,30] (matrices A1..A4). Find the cheapest way to parenthesize A1..A4 to minimize total scalar multiplications.

Problem:Matrix Chain MultiplicationHard

dp[i][j] = min over split k of dp[i][k] + dp[k+1][j] + dims[i-1]*dims[k]*dims[j]

step 1 / 9

dp[i][j] = min scalar multiplications to multiply matrices i..j

A1A2A3A4

A single matrix needs no multiplication, so dp[i][i] = 0 for every one of the 4 matrices.

Pseudocode

1FUNCTION matrixChainOrder(dims):
2  n <- LENGTH(dims) - 1
3  FOR i FROM 1 TO n:
4    dp[i][i] <- 0
5  FOR length FROM 2 TO n:
6    FOR i FROM 1 TO n - length + 1:
7      j <- i + length - 1
8      dp[i][j] <- INFINITY
9      FOR k FROM i TO j - 1:
10        cost <- dp[i][k] + dp[k+1][j] + dims[i-1] * dims[k] * dims[j]
11        IF cost < dp[i][j]:
12          dp[i][j] <- cost
13  RETURN dp[1][n]

← / → step · space play · Home restart

Every step in words

Show all 9 steps

A single matrix needs no multiplication, so dp[i][i] = 0 for every one of the 4 matrices.
Splitting A1..A2 at A1 | A2..A2 costs 0 + 0 + 40*20*30 = 24000, the best split for dp[1][2] so far.
Splitting A2..A3 at A2 | A3..A3 costs 0 + 0 + 20*30*10 = 6000, the best split for dp[2][3] so far.
Splitting A3..A4 at A3 | A4..A4 costs 0 + 0 + 30*10*30 = 9000, the best split for dp[3][4] so far.
Splitting A1..A3 at A1 | A2..A3 costs 0 + 6000 + 40*20*10 = 14000, the best split for dp[1][3] so far.
Splitting A2..A4 at A2 | A3..A4 costs 0 + 9000 + 20*30*30 = 27000, the best split for dp[2][4] so far.
Splitting A2..A4 at A3 | A4..A4 costs 6000 + 0 + 20*10*30 = 12000, the best split for dp[2][4] so far.
Splitting at A1 | A2..A4 costs 0 + 12000 + 40*20*30 = 36000, the best way to close the whole chain: dp[1][4] = 36000.
Splitting at A3 | A4..A4 costs 14000 + 0 + 40*10*30 = 26000, the best way to close the whole chain: dp[1][4] = 26000.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Matrix Chain Multiplication in the editor All Dynamic Programming problems Back to roadmap