##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
Finding optimal parenthesization
The DP gives minimum cost, but what's the optimal order? Track the split point. When computing , record where the minimum occurs.
Reconstruct recursively: = "(" + + + ")". For our example: , so optimal is . Store the split point in a separate array. Reconstruct by recursively printing the optimal parenthesization.
