Matrix Chain Multiplication
Given matrix dimensions where matrix i is dims[i-1] x dims[i], find the fewest scalar multiplications needed to multiply the whole chain.
Intuition
Matrix multiplication is associative, so every parenthesisation yields the same product — but the cost varies wildly, sometimes by orders of magnitude. The last multiplication performed splits the chain into a left half and a right half, each of which must already be reduced to a single matrix. So the cost of a chain is the cost of its two halves plus one final multiply of dims[i-1] x dims[k] x dims[j]. Trying every split point k gives the answer, and because both halves are strictly shorter, the table must be filled by increasing chain length rather than in reading order.
Approach
State over intervals
dp[i][j] = minimum multiplications to reduce matrices i..j to one matrix. A single matrix needs no work, so the diagonal is zero.
Try every split
dp[i][j] = min over k in i..j-1 of dp[i][k] + dp[k+1][j] + dims[i-1]·dims[k]·dims[j]. The last term is the cost of combining the two resulting matrices.
Fill by length, not by row
Every split reads shorter intervals, so iterate span = 2..n and slide i across. Filling row by row would read cells that are not final yet.
Solution & live demo
Edge cases
dp[1][1] = 0 — nothing to multiply.
Exactly one split exists, so the answer is the single product dims[0]·dims[1]·dims[2].
The result is a multiplication count; the matrix product itself is identical under every parenthesisation.