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.