Matrix Chain Multiplication - Transition

To compute $dp[i][j]$, try every split point $k$ from $i$ to $j-1$. Splitting at $k$ means you first compute $(M_i \ldots M_k)$, then $(M_{k+1} \ldots M_j)$, then multiply the results.

Cost = $dp[i][k] + dp[k+1][j] + dims[i-1] \times dims[k] \times dims[j]$. The last term is the cost of multiplying the two resulting matrices.

Take the minimum over all $k$:

$dp[i][j] = \min_{i \le k < j} \left( dp[i][k] + dp[k+1][j] + dims[i-1] \times dims[k] \times dims[j] \right)$