Exercise 15.2.2

Give a recursive algorithm MATRIX-CHAIN-MULTIPLY(A, s, i, j) that actually performs the optimal matrix-chain multiplication, given the sequence of matrices $\langle A_1, A_2, \ldots, A_n \rangle$, the $s$ table computed MATRIX-CHAIN-ORDER, and the indices $i$ and $j$. (The initial call would be MATRIX-CHAIN-MULTIPLY(A, s, 1, n).)

Unless I'm missing something really clever, this is either super trivial, or a big annoyance in managing memory.

The best way to do it is to just modify PRINT-OPTIMAL-PARENS to do the multiplication. The recursive structure of the algorithm is the same.