[idea] dynamic planning (DP)

One 、 Introduce

1.1、 history

Simply remember ,20 century 50 American mathematician Richard in the s · Invented by Behrman , It is an important tool for solving some optimal problems in mathematics , And in the computer field as a general algorithm design technology . For the rest of the history, please refer to MIT textbooks Dynamic Programming Part 1 .

1.2、 Definition

【 a key 】 If the problem is caused by Overlapping subproblems Composed of , Then we can use dynamic programming technology to solve it .

Generally speaking , The subproblem appears in the recurrence relation of solving a given problem , This recurrence relation contains the solutions of the same type of more sub problems .DP It is suggested to solve the overlapping subproblems again and again , It is better to solve each smaller subproblem only once and record the results in the table , In this way, the solution of the original problem can be obtained from the table .

1.3、 Familiar with mathematical applications

Classical problems of Fibonacci numbers

0,1,1,2,3,5,8,13,21,34....

What is the law that we can find out ？

【0】= 0,【1】=1,【2】=1,【3】=2,【4】=3

Disassemble the problem , Find overlapping sub problems （ Color area ）, According to our definition , If the problem is composed of overlapping subproblems , Then we can use dynamic programming technology to solve .

Then we define the subproblem, for example, we ask F(n)=F(n-1)+F(n-2), Then guess whether all the results are satisfied according to our formula . Find out n=0/1 When , dissatisfaction . So we need to adjust the formula . The following pseudo code ：

function(int n){
    // Recursive exit condition 
    if (n < 1){
       return n;
    }else{
        // recursive 
       return function(n-1)+function(n-2);
    }
}

But the problem we mentioned earlier , In essence, our recursive code above has already realized the basic functions , According to the above figure, we calculate F(4) When , Need to compute F(3) and F(2), But many overlapping subproblems are found , How to solve double counting ？ We can assume that whatever F(2) and F(3) Who will execute first , Keep the results of the previous execution in memory , Then you can directly obtain the following information when performing the calculation , So you can avoid double counting . Let's modify the pseudo code ：

mem = {}
function(int n){
    // Memorize , Avoid solving calculations repeatedly 
    if(n in mem) return mem[n];
    // Recursive exit condition 
    if (0 <= n < 1){
       return n;
    }else{
       // The solution of memory storage subproblem  
       mem[n] = function(n-1)+function(n-2);
       // recursive  
       return function(n-1)+function(n-2);
    }
}

So how was the original problem solved ？ In fact, we use the bottom-up logic when n=0/1 When , Start computing from the recursive stack , Until the result .

Two 、 Step suggestions

2.1、 Dynamic planning steps 5

1. Define subproblems ( Personal understanding is to disassemble the problem first , Disassembly to the smallest unit is the subproblem )
2. guess （ Part of the solution , Derive the calculation formula ）
3. Solutions to related sub problems （ Solutions to local problems ）
4. recursive + memory （ Solve the problem of double counting ）
5. Or build DP The table checks the loop of sub problems from bottom to top / Topological order （ State transition equation ）
6. Solve the original problem ：= Solve subproblems or by combining subproblems => Extra time

source ： MIT derived steps for dynamic programming , Dynamic Programming Part 1 , Dynamic Programming Part II

2.2、 Refine next step

1、 Define subproblems - Problem disassembly

2、 Building recursive formulas （ recursive + Memorize ==> Recurrence ）

3、 Bottom up treatment （ State transition equation ）

4、DP ≈ recursive + Memorize + guess

3、 ... and 、 Learning route

• Currency maximization
• Coin change problem （ Greedy Algorithm ）
• Coin collection
• Recurrence of violence （ Greedy failure ）
• Avoid recursive double counting （ Recurrence = recursive + Memorize ）
• knapsack problem
• Completely backpack
• Subarray problem
• Subsequence problem
• Buying and selling stocks
• The longest increasing subsequence problem
• Maximum subarray problem
• Optimal substructure and state dependence

This paper explains the deduction of the idea of dynamic programming and the path of learning and practice , The following will add practical algorithm topics ！