# How does matrix chain multiplication problem has an optimal substructure?

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?

• It's unclear to me what your question is. You say "If any of above is optimal solution..." but how would you know it's optimal? You would have to compare it to other subsctructures like (((A1.A2)A3)(A4.A5))(A6.An) – Albert Hendriks Mar 24 '18 at 11:44
• I was just assuming the worst case where the optimal solution is, let's assume, (((((A1.A2)A3)A4)A5)A6)An). This made me wonder if the problem actually had any substructure and we consider dp to solve it. But now I understood, if the optimal solution is any other solution that worst case, that has optimal substructure. – Sachin Verma Mar 24 '18 at 14:30