dynamic programming the important fact to observe is that we have attempted to solve maximization problem involving particular value of and particular value of by first solving the general problem involving an arbitrary value of and an arbitrary value of -"dynamic programming, bellman dp is general technique for solving optimizationsearchand counting problems that can be decomposed into subproblems you should consider using dp whenever you have to make choices to arrive at the solutionspecificallywhen the solution relates to subproblems like divide-and-conquerdp solves the problem by combining the solutions of multiple smaller problemsbut what makes dp different is that the same subproblem may reoccur thereforea key to making dp efficient is caching the results of intermediate computations problems whose solutions use dp are popular choice for hard interview questions to illustrate the idea underlying dpconsider the problem of computing fibonacci numbers the first two fibonacci numbers are and successive numbers are the sums of the two previous numbers the first few fibonacci numbers are the fibonacci numbers arise in many diverse applications--biologydata structure analysisand parallel computing are some examples mathematicallythe nth fibonacci number (nis given by the equation (nf( ( )with ( and ( function to compute (nthat recursively invokes itself has time complexity that is exponential in this is because the recursive function computes some ( ) repeatedly figure on the following page graphically illustrates how the function is repeatedly called with the same arguments caching intermediate results makes the time complexity for computing the nth fibonacci number linear in nalbeit at the expense of (nstorage def fibonacci (ncache ={})if < return elif not in cache cache [nfibonacci ( fibonacci ( return cache [nminimizing cache space is recurring theme in dp now we show program that computes (nin (ntime and ( space conceptuallyin contrast to the above programthis program iteratively fills in the cache in bottom-up fashionwhich allows it to reuse cache storage to reduce the space complexity of the cache def fibonacci ( )