What is Dynamic Programming ?

Introduction

Dynamic programming,like the divide-and-conquer method,solves problems by combining the solutions to sub problems.("Programming" in this context refers to  a tabular method,not to writing computer code.)In  divide-and-conquer algorithms partition the problem into  independent sub problems,solve the sub problems recursively and then combine their solutions to solve the original problem.In contrast,dynamic programming is applicable when the sub problems are not independent,that is ,when sub problems share sub-sub problems.In this context,a divide-and-conquer algorithm does more work than necessary,repeatedly solving the common sub sub problems.A dynamic programming algorithm solves every sub-sub problem just once and then saves its answer in a table,thereby avoiding the work of recomputing the answer every time the sub-sub problems in encountered.

   Dynamic programming is typically applied to optimization problems.In sub problems there can be many possible solutions.each solution has a value,and we wish to find a solution with the optimal(minimum or maximum)value.We call such a solution an optimal solutions to the problem,as opposed to the optimal solution,since there may be several solutions that achieve the optimal value.

 The development of a dynamic-programming algorithm can be broken into a sequence of four steps.

  1.Characterize the structure of an optimal solution.
  2.Recursively defines the value of an optimal solution.
  3.Compute the value of an optimal solution in a bottom-up fashion.
  4.Construct an optimal  solution from computed information.

Steps 1-3 form the basis of a dynamic-programming solution to a problem.Step 4 can be omitted if only the value of an optimal solution is required.When we do perform step 4,we sometimes maintain additional information during the computation in step 3 to ease the construction of an optimal solution.

Elements of Dynamic Programming

               From an engineering perspective,when should we look for a dynamic programming solution to a problem?In this section,we examine the two key ingredients that an optimization problem must have for dynamic programming to be applicable:optimal substructure and overlapping sub problems. 

Optimal substructure

  The first step in solving an optimization problem by dynamic programming is to characterize the structure of an optimal solution.We say that a problem exhibits optimal substructure if an optimal solutions to sub problems.Whenever a problem exhibits optimal substructure,it is a good clue that dynamic programming might apply.(It also might mean that a greedy strategy applies)

              We observed that an optimal anesthetization of A1A2...An that splits the product between Ak and Ak+1 contains within it optimal solutions to the problems of parenthesizing A1A2....Ak and Ak+1Ak+2....An.The technique that we used t oshow that sub problems have optimal solutions is typical.The optimal substructure of a problem foten suggests a asuitable space of sub problems to which dynamic programming can be applied.

Overlapping sub problems

The second ingredient that an optimization that an optimization problem must have for dynamic programming to be applicable is that the space of sub problems must be "small" in the sense that a recursive algorithm for the problem solves the same sub problems over and over,rather than always generating new sub problems.Typically,the total number of distinct sub problems is a polynomial in the input size.When a recursive algorithm revisits same problem over and over again,we say that the optimization problem has overlapping sub problems.In contrast,a problem for which a divide and -conquer approach is suitable usually generates brand new problems at each step of the recursion.Dynamic programming algorithms typically take advantage of overlapping sub  problems by solving each sub problems once and then storing the solution in a table where it can be looked up when needed,using constant time per lookup.