function matrixChainOrder(dims, n)
dp := 2D array [n+1][n+1], all 0
for len from 2 to n
for i from 1 to n - len + 1
j := i + len - 1
dp[i][j] := infinity
for k from i to j - 1
cost := dp[i][k] + dp[k+1][j] + dims[i-1] * dims[k] * dims[j]
if cost < dp[i][j]
dp[i][j] := cost
return dp[1][n]
Fill by increasing chain length so that shorter chains are solved before longer ones. The answer sits at .
Time complexity: .
Space complexity: for the DP table.