defining subproblems one way to solve the matrix chain-product problem is to simply enumerate all the possible ways of parenthesizing the expression for and determine the number of multiplications performed by each one unfortunatelythe set of all different parenthesizations of the expression for is equal in number to the set of all different binary trees that have leaves this number is exponential in thusthis straightforward ("brute-force"algorithm runs in exponential timefor there are an exponential number of ways to parenthesize an associative arithmetic expression we can significantly improve the performance achieved by the brute-force algorithmhoweverby making few observations about the nature of the matrix chain-product problem the first is that the problem can be split into subproblems in this casewe can define number of different subproblemseach of which is to compute the best parenthesization for some subexpression ai ai+ as concise notationwe use nij to denote the minimum number of multiplications needed to compute this subexpression thusthe original matrix chain-product problem can be characterized as that of computing the value of , - this observation is importantbut we need one more in order to apply the dynamic programming technique characterizing optimal solutions the other important observation we can make about the matrix chain-product problem is that it is possible to characterize an optimal solution to particular subproblem in terms of optimal solutions to its subproblems we call this property the subproblem optimality condition in the case of the matrix chain-product problemwe observe thatno matter how we parenthesize subexpressionthere has to be some final matrix multiplication that we perform that isa full parenthesization of subexpression ai ai+ has to be of the form (ai ak (ak+ )for some {ii moreoverfor whichever is the correct onethe products (ai ak and (ak+ must also be solved optimally if this were not sothen there would be global optimal that had one of these subproblems solved suboptimally but this is impossiblesince we could then reduce the total number of multiplications by replacing the current subproblem solution by an optimal solution for the subproblem this observation implies way of explicitly defining the optimization problem for nij in terms of other optimal subproblem solutions namelywe can compute nij by considering each place where we could put the final multiplication and taking the minimum over all such choices