Chain Matrix Multiplication Each order of multiplication corresponds to a parenthesization (A1(A2A3(A4(AsA6)A7) Optimal substructure If the above parenthesization is optimal,then .(A(A2A3))is optimal for multiplying A1,...A3 .(A((AsA )A))is optimal for multiplying Aa,...,A .((AsA)A)is optimal for multiplying As,...,A -Every“"subparenthesization”of an optimal parenthesization is optimalChain Matrix Multiplication • Each order of multiplication corresponds to a parenthesization ((A1 (A2A3 ))(A4 ((A5A6 )A7 ))) • Optimal substructure – If the above parenthesization is optimal, then • (A1 (A2A3 )) is optimal for multiplying A1 , …, A3 • (A4 ((A5A6 )A7 )) is optimal for multiplying A4 , …, A7 • ((A5A6 )A7 )is optimal for multiplying A5 , …, A7 – Every “subparenthesization” of an optimal parenthesization is optimal