the solution of this recurrence is the well-known catalan numberswhich grow exponentially thusfor large nan exhaustive search through all possible orderings is useless neverthelessthis counting argument provides basis for solution that is substantially better than exponential let ci be the number of columns in matrix ai for < < then ai has ci- rowssince otherwise the multiplications are not valid we will define to be the number of rows in the first matrixa suppose mleftright is the number of multiplications required to multiply aleft aleft+ aright- aright for consistencymleftleft suppose the last multiplication is (aleft ai )(ai+ aright )where left < right then the number of multiplications used is mlefti mi+ right cleft- ci cright these three terms represent the multiplications required to compute (aleft ai )(ai+ aright )and their productrespectively if we define mleftright to be the number of multiplications required in an optimal orderingthenif left rightmleftright min {mlefti mi+ right cleft- ci cright left<= <right this equation implies that if we have an optimal multiplication arrangement of aleft aright the subproblems aleft ai and ai+ aright cannot be performed suboptimally this should be clearsince otherwise we could improve the entire result by replacing the suboptimal computation by an optimal computation the formula translates directly to recursive programbutas we have seen in the last sectionsuch program would be blatantly inefficient howeversince there are only approximately / values of mleftright that ever need to be computedit is clear that table can be used to store these values further examination shows that if right left kthen the only values mxy that are needed in the computation of mleftright satisfy - this tells us the order in which we need to compute the table if we want to print out the actual ordering of the multiplications in addition to the final answer , then we can use the ideas from the shortest-path algorithms in whenever we make change to mleftright we record the value of that is responsible this gives the simple program shown in figure although the emphasis of this is not codingit is worth noting that many programmers tend to shorten variable names to single letter ciand are used as single-letter variables because this agrees with the names we have used in the description of the algorithmwhich is very mathematical howeverit is generally best to avoid as variable namebecause looks too much like and can make for very difficult debugging if you make transcription error returning to the algorithmic issuesthis program contains triply nested loop and is easily seen to run in ( time the references describe faster algorithmbut since the time to perform the actual matrix multiplication is still likely to be much larger than the time to compute the optimal orderingthis algorithm is still quite practical optimal binary search tree our second dynamic programming example considers the following inputwe are given list of wordsw wn and fixed probabilitiesp pn of their occurrence