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.