We solve Matrix chain multiplication problem considering the optimal solution to subproblems but what I cant get through my mind is how this problem has an optimal substructure?
For eg. consider if these are optimal solutions for matrices A1.A2.A3.A4.A5.An:
(((((A1.A2)A3)A4)A5)A6)An)
(((((A1.A2)A3)A4)A5)(A6.An))
If any of above is optimal solution then we won't be able to consider any optimal substructre.No?