# 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.