A chain of matrices needs to be multiplied together in order — matrix 1 by matrix 2 by matrix 3 and so on — but matrix multiplication only cares about doing the pairs in the right order, not which pair gets combined first. Because it's associative, `(A1 A2) A3` and `A1 (A2 A3)` produce the identical final matrix, yet the number of individual number-multiplications spent getting there can differ enormously depending on the sizes involved. Given the dimensions of each matrix in the chain (as an array `p` where matrix i is p[i-1]×p[i]), find the cheapest possible parenthesization. The key structural fact: whatever the best full parenthesization turns out to be, it has some *last* multiplication — a single split point where everything to its left became one matrix and everything to its right became another. That means the best way to combine matrices i through j is entirely determined by the best way to combine i through some k, the best way to combine k+1 through j, and the cost of that one final multiply — for whichever k turns out cheapest. Solving every sub-chain from the shortest upward, and reusing each answer rather than re-deriving it, turns an exponential search into a cubic one.