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?

First of all, it is correct and important to know that optimal solutions need not necessarily be unique!
However, this doesn't mean we cannot have optimal substructure. Recall what optimal substructure means: the structure is such that if we know to make an 'optimal' decision on some 'local' criterion, we can get the actual 'global' optimum by making such decisions repeatedly (usually via divide and rule)

Note that again, the 'optimal' decision need not be unique! So, by making different locally optimal decisions, it is possible to end up with multiple globally optimal results. So, the seeming contradiction of multiple optima and optimal substructure doesn't exist.

StackExchange Computer Science Q#89454, answer score: 5