designing dynamic programming algorithm we can therefore characterize the optimal subproblem solutionnij as nij min {ni, nk+ di dk+ + } <=kj where ni, since no work is needed for single matrix that isnij is the minimumtaken over all possible places to perform the final multiplicationof the number of multiplications needed to compute each subexpression plus the number of multiplications needed to perform the final matrix multiplication notice that there is sharing of subproblems going on that prevents us from dividing the problem into completely independent subproblems (as we would need to do to apply the divide-and-conquer techniquewe canneverthelessuse the equation for nij to derive an efficient algorithm by computing nij values in bottom-up fashionand storing intermediate solutions in table of nij values we can begin simply enough by assigning ni, for we can then apply the general equation for nij to compute ni, + valuessince they depend only on ni, and ni+ , + values that are available given the ni, + valueswe can then compute the ni, + valuesand so on thereforewe can build nij values up from previously computed values until we can finally compute the value of , - which is the number that we are searching for python implementation of this dynamic programming solution is given in code fragment we use techniques from section for representing multidimensional table in python def matrix chain( ) """ is list of + numbers such that size of kth matrix is [ ]-by- [ + return an -by- table such that [ ][jrepresents the minimum number of multiplications needed to compute the product of ai through aj inclusive "" len( number of matrices initialize -by- result to zero [[ for in range( ) for in range( )number of products in subchain for in range( - )start of subchain = + end of subchain [ ][jmin( [ ][ ]+ [ + ][ ]+ [id[ + [ + for in range( , ) return code fragment dynamic programming algorithm for the matrix chainproduct problem thuswe can compute , - with an algorithm that consists primarily of three nested loops (the third of which computes the min termeach of these loops iterates at most times per executionwith constant amount of additional work within thereforethe total running time of this algorithm is (