Pattern visualizer

Matrix Chain Multiplication

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. Animated on: dims = [40,20,30,10,30] (matrices A1..A4). Find the cheapest way to parenthesize A1..A4 to minimize total scalar multiplications..

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)step 1 / 9

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

A1A2A3A4

line 4

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

Where to practice Dynamic Programming

Practice Dynamic Programming problems All Dynamic Programming problems Back to roadmap