dynamic programming in this sectionwe discuss the dynamic programming algorithm-design technique this technique is similar to the divide-and-conquer technique (section )in that it can be applied to wide variety of different problems dynamic programming can often be used to take problems that seem to require exponential time and produce polynomial-time algorithms to solve them in additionthe algorithms that result from applications of the dynamic programming technique are usually quite simple--often needing little more than few lines of code to describe some nested loops for filling in table matrix chain-product rather than starting out with an explanation of the general components of the dynamic programming techniquewe begin by giving classicconcrete example suppose we are given collection of two-dimensional matrices for which we wish to compute the mathematical product an- where ai is di di+ matrixfor in the standard matrix multiplication algorithm (which is the one we will use)to multiply -matrix times an -matrix cwe compute the productaas - [ ]jb[ ][ * [ ]jk= this definition implies that matrix multiplication is associativethat isit implies that ( ( cd thuswe can parenthesize the expression for any way we wish and we will end up with the same answer howeverwe will not necessarily perform the same number of primitive (that isscalarmultiplications in each parenthesizationas is illustrated in the following example example let be -matrixlet be -matrixand let be -matrix computing ( drequires multiplicationswhereas computing ( *cd requires multiplications the matrix chain-product problem is to determine the parenthesization of the expression defining the product that minimizes the total number of scalar multiplications performed as the example above illustratesthe differences between parenthesizations can be dramaticso finding good solution can result in significant speedups