dynamic programming was invented by richard bellman in the early don' try to infer anything about the technique from its name as bellman described itthe name "dynamic programmingwas chosen to hide from governmental sponsors "the fact that was really doing mathematics [the phrase dynamic programmingwas something not even congressman could object to " dynamic programming is method for efficiently solving problems that exhibit the characteristics of overlapping subproblems and optimal substructure fortunatelymany optimization problems exhibit these characteristics problem has optimal substructure if globally optimal solution can be found by combining optimal solutions to local subproblems we've already looked at number of such problems merge sortfor exampleexploits the fact that list can be sorted by first sorting sublists and then merging the solutions problem has overlapping subproblems if an optimal solution involves solving the same problem multiple times merge sort does not exhibit this property even though we are performing merge many timeswe are merging different lists each time it' not immediately obviousbut the / knapsack problem exhibits both of these properties before looking at thathoweverwe will digress to look at problem where the optimal substructure and overlapping subproblems are more obvious fibonacci sequencesrevisited in we looked at straightforward recursive implementation of the fibonacci functionshown here in figure def fib( )"""assumes is an int > returns fibonacci of ""if = or = return elsereturn fib( - fib( - figure recursive implementation of fibonacci function as quoted in stuart dreyfus "richard bellman on the birth of dynamic programming,operations researchvol no (