On dynamic programming

Concept

Dynamic programming （Dynamic Programming,DP） It is the process of solving the optimization of decision-making process . A method of solving complex problems by decomposing the original problem into relatively simple subproblems . In the backpack problem 、 Production and operation problems 、 Money management issues 、 The allocation of resources 、 The shortest path problem and the reliability problem of complex systems are widely used .

In my student days acm competition , Is a required algorithm topic , It is also the algorithm question that appears most frequently in the interview of large technology companies , Many types of topics , No fixed template , Very flexible , It's hard to think , The difficulty is in the upper middle , There is no obvious routine .

In fact, learn dynamic planning well , It's not just about mastering the algorithm model , And for ourselves , Use a dynamic planning idea to deal with our own affairs and problems , Or you can put this idea into your life , Put it in your frustration , Very skillful and interesting , If you have this in mind , It's a lot easier .

Algorithm implementation description

Dynamic algorithm and divide and conquer algorithm , The recursive algorithm is similar to , The basic idea is to decompose the problem to be solved into several sub problems , First solve the subproblem , Then the solution of the original problem is obtained from the solution of these subproblems . What's different from divide and conquer is , The decomposed subproblems are not independent of each other , Some subproblems are interdependent , Repeat the calculation to solve . It depends on whether the problem can be solved by dynamic programming .

Three elements

• The stage of the problem

• The state of each phase

• The recursive relationship between the previous stage and the later stage .

The recurrence relation must be transformed from the problem with small order to the problem with large order , So dynamic programming can be solved by recursion .

The whole solving process can be described by an optimal decision table , The optimal decision table is a two-dimensional table , Where the line represents the stage of the decision , The list shows the status of the problem , Form needs