Problem
We are given a sequence of matrices to multiply: The cost of multiplying an nxm by an mxp one is O(nmp) (or O(n^{3}) for two nxn ones). A poor choice of parenthesisation can be expensive: eg if we have
Matrix  Rows  Columns 

A_{1}  10  100 
A_{2}  100  5 
A_{3}  5  50 
A_{1}A_{2}  10x100x5  = 5000  => A_{1} A_{2} (10x5) 
(A_{1}A_{2}) A_{3}  10x5x50  = 2500  => A_{1}A_{2}A_{3} (10x50) 
Total  7500 
A_{2}A_{3}  100x5x50  = 25000  => A_{2}A_{3} (100x50) 
A_{1}(A_{2}A_{3})  10x100x50  = 50000  => A_{1}A_{2}A_{3} (10x50) 
Total  75000 
Optimal Substructure
As with the optimal binary search tree, we can observe that if we divide a chain of matrices to be multiplied into two optimal subchains: This property, known as optimal substructure is a hallmark of dynamic algorithms: it enables us to solve the small problems (the substructure) and use those solutions to generate solutions to larger problems.
For matrix chain multiplication, the procedure is now almost identical to that used for constructing an optimal binary search tree. We gradually fill in two matrices,
 one containing the costs of multiplying all the subchains. The diagonal below the main diagonal contains the costs of all pairwise multiplications: cost[1,2] contains the cost of generating product A_{1}A_{2}, etc. The diagonal below that contains the costs of triple products: eg cost[1,3] contains the cost of generating product A_{1}A_{2}A_{3}, which we derived from comparing cost[1,2] and cost[2,3], etc.
 one containing the index of last array in the left parenthesisation (similar to the root of the optimal subtree in the optimal binary search tree, but there's no root here  the chain is divided into left and right subproducts), so that best[1,3] might contain 2 to indicate that the left subchain contains A_{1}A_{2} and the right one is A_{3} in the optimal parenthesisation of A_{1}A_{2}A_{3}.
As before, if we have n matrices to multiply, it will take O(n) time to generate each of the O(n^{2})best matrix for an overall complexity of O(n^{3}) time at a cost of O(n^{2}) costs and entries in the space.
Key terms 
