Similarities: the basic idea is to decompose the problem to be solved into several sub-problems, solve the sub-problems first, and then get the solution of the original problem from the solutions of these sub-problems;

Difference:

(1) is suitable for the problem solved by dynamic programming method, and the subproblems obtained by decomposition are often not independent of each other. If this kind of problem is solved by divide and conquer, the number of sub-problems obtained by decomposition is so large that it takes exponential time to finally solve the original problem;

(2) The number of different subproblems is often only polynomial, and some subproblems need to be calculated repeatedly when they are solved by divide-and-conquer method. The dynamic programming method saves the answers to the solved sub-problems and looks for the obtained answers when necessary, which can avoid a lot of repeated calculations and thus get a polynomial time algorithm.

The concept of dynamic programming:

Dynamic programming (DP) is a branch of operational research, which aims to solve? Optimization of decision-making process? This process. In the early 1950s, American mathematician R.Bellman and others put forward the famous optimization principle when studying the optimization problem of multi-stage decision-making process, thus creating dynamic programming.

Dynamic programming is widely used, including engineering technology, economy, industrial production, military and automation control, and has made remarkable achievements in knapsack problem, production management problem, fund management problem, resource allocation problem, shortest path problem and complex system reliability problem.

Although dynamic planning is mainly used to solve the optimization problem of dynamic process with time division, some static planning that has nothing to do with time (such as? Linear programming, nonlinear programming? ), as long as the time factor is artificially introduced, it can be regarded as a multi-stage decision-making process, and it can also be easily solved by dynamic programming method.