Matrix Chain Multiplication - Implementation

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 $dp[1][n]$.

Time complexity: $O(n^3)$.

Space complexity: $O(n^2)$ for the DP table.