The basic concept

Dynamic programming is a process in which each decision depends on the current state and then causes a state transition. A decision sequence is produced in the changing state, so the process of multi-stage optimization decision solving problem is called dynamic programming.

Basic ideas and strategies

The basic idea is similar to the divide-and-conquer method. The problem to be solved is decomposed into several sub-problems (stages), and the sub-stages are solved in sequence. The solution of the former sub-problem provides useful information for the solution of the latter sub-problem. When solving any sub-problem, all kinds of possible local solutions are listed, and those local solutions that are likely to be optimal are retained through decision making, while others are discarded. Each subproblem is solved in turn, and the last subproblem is the solution of the original problem.

Since most problems solved by dynamic programming have overlapping sub-problems, in order to reduce repeated calculation, each sub-problem is solved only once and different states at different stages are saved in an appropriate data structure, such as one-dimensional array and two-dimensional array.

The biggest difference with divide-and-conquer method is that it is suitable for solving problems with dynamic programming method, and the sub-problems obtained after decomposition are often not independent of each other (that is, the solution of the next sub-stage is based on the solution of the previous sub-stage for further solution).

Applicable circumstances

Problems that can be solved by dynamic programming generally have three properties:

  • Optimization principle: if the optimal solution of the problem contains the solution of the subproblem is also optimal, the problem is said to have the optimal substructure, that is, to satisfy the optimization principle.
  • No aftereffect: that is, once the state of a certain stage is determined, it is not affected by the subsequent decision of this state. That is, a process after a state does not affect the previous state, only the current state.
  • Overlapping subproblems: that is, subproblems are not independent, and a subproblem may be used more than once in the next stage of decision making. (This property is not necessary for dynamic programming, but without this property, dynamic programming algorithms have no advantage over other algorithms.)

The basic steps of the solution

The problem that dynamic programming deals with is a multi-stage decision problem. It usually starts from the initial state and reaches the end state through the choice of the intermediate stage decision. These decisions form a sequence of decisions and define a course of action (usually the optimal course of action) to complete the process. As shown in the figure. The design of dynamic programming has a certain pattern, which generally goes through the following steps.

Initial status →│ Decision 1│ Decision 2│… →│ decision n│ end state

  • Stages: To divide a problem into stages according to its temporal or spatial characteristics. When dividing the stages, note that the stages after dividing must be ordered or sortable, otherwise the problem cannot be solved.

  • Determine the state and state variables: the development of the problem to each stage of the various objective situations in different states. Of course, the choice of states should satisfy no aftereffect.

  • Determine the decision and write down the state transition equation: because there is a natural connection between decision and state transition, state transition is to derive the state of the current stage according to the state and decision of the previous stage. So if the decision is made, the state transition equation can also be written. But in practice it is often done the other way around, determining the decision method and the state transition equation based on the relationship between the states of the two adjacent phases.

  • Looking for boundary conditions: The given state transition equation is a recursive expression that requires a recursive termination condition or boundary condition.

In general, the state transition equation (including boundary conditions) can be written as long as the stage, state and state transition decision of solving the problem are determined.

In practical application, the design can be carried out according to the following simplified steps:

  • The properties of the optimal solution are analyzed and its structural characteristics are described.
  • Recursive definition of the optimal solution.
  • The optimal value is calculated in a bottom-up or top-down memorization method (memento method)
  • According to the information obtained when calculating the optimal value, the optimal solution of the problem is constructed

Description of algorithm implementation

The main difficulty of dynamic planning lies in the theoretical design, that is, the determination of the above four steps. Once the design is completed, the implementation part will be very simple.

Using dynamic programming to solve problems, the most important is to determine the three elements of dynamic programming

  • Stage of the problem
  • The state of each phase
  • A recursive relationship between transitions from one stage to the next.

Recursive relations must starts from the minor problems to the transformation of the larger problem between, from this perspective, the dynamic programming often can use recursive procedure to implement, but because of recursive can make full use of the previously stored subproblem solutions to reduce the repeated computation, so for large-scale problem, a recursive incomparable advantages, it is also the core of the dynamic programming algorithm.

Determine the three elements of the dynamic programming, the whole solving process can be described using an optimal decision table, the optimal decision table is a two-dimensional table, which represents the decision-making stage, columns represent problem, need to fill in the form data is corresponding to the problem in a certain stage of the optimal value of a state (such as the shortest path, the longest common subsequence, maximum value, etc.), The process of filling the table is to fill in the table in order of row or column priority, starting from row 1 and column 1 according to the recursive relationship. Finally, the optimal solution of the problem is obtained through simple trade-off or operation according to the data of the whole table.

Basic framework of dynamic programming algorithm

for(j=1; j<=m; j=j+1) // The first stageXn [J] = initial value;for(i=n-1; i>=1; i=i-1)// Other n-1 phases
   for(j=1; j>=f(i); j=j+1)//f(I) is an expression related to IXi [j]=j= Max (or min) {g(xi-1[j1:j2]), ...... , g(xi-1[jk:jk+1])};

t = g(x1[j1:j2]); // The optimal solution of the whole problem is solved by the optimal solution of the subproblem

print(x1[j1]);

for(i=2; i<=n-1; i=i+1) {t = t-xi-1[ji];

     for(j=1; j>=f(i); j=j+1)
        if(t=xi[ji])
             break;
}
Copy the code

reference

Common Algorithm Strategies