当前位置：网站首页>Theory + practice will help you master the dynamic programming method

Theory + practice will help you master the dynamic programming method

2022-06-12 23:30:00 【Huawei cloud developer community】

This article is shared from Huawei cloud community 《 Five basic algorithms -- Dynamic programming 》, author ： daikin （ Inner Mongolia ）.

One 、 Basic concepts

Dynamic programming , Very similar to divide and conquer . The difference is , In solving subproblems , The solution of the subproblem will be saved , When solving the following subproblem , Can be directly used to calculate .

The professional term is ：

For a scale of n The problem of , Break it down into k A smaller sub problem （ Stage ）, Solve the subproblems in order , The solution of the previous subproblem , It provides useful information for the solution of the latter subproblem . In solving any subproblem , The local optimal solution is obtained through decision-making , Solve each sub problem in turn . Finally, you can make a simple judgment , Get the solution of the original problem .

It's hard to understand , Let me explain to you ：

Stage ： Solving the second problem n The subproblem is called the second n Stages . Dynamic programming is to solve subproblems in order , Here, the order of solving subproblems is very important .

state ： In solving the problem of n In the next stage , Solved n-1 The solution of two stages , It's called state .

Decision making ： In solving the problem of n In the next stage , According to the state and calculation rules , You can get the n Time solution of two stages .

Two 、 basic feature

The problems that can be solved by dynamic programming method generally have the following characteristics ：

1) Big problem decomposability

The problem can be decomposed into several On a smaller scale The problem of , That is, the problem has the property of optimal substructure .

2) Sub problem solvability

The problem can be easily solved by reducing its scale to a certain extent

3) Solution mergeability

The solution of the subproblem can be combined into the solution of the problem ;

4) The overlapping of subproblems

When calculating the solution of a subproblem , The solution of the subproblem needs to be calculated for many subsequent problems , So when calculating the solution of a subproblem , Save it , It saves the time of repeated calculation of divide and conquer method .

3、 ... and 、 Some misunderstandings

1. State transition equation

Many blogs talk about the state transition equation , I feel it's very tall , The general solution is that the state transition equation is xxxx, The code is xxxx, What does it mean to translate ？

In solving the problem of n When it comes to sub problems , By solving n-1 Solution and calculation rules of three stages , You can get the n Time solution of two stages .

That is, the latest state = The current state + Decision making .

2. initialization

Many problems say initialization when solving problems , This is not a step of dynamic programming . These operations should be understood correctly . Dynamic programming is used to divide the solving order of subproblems , Basically, we first solve the smallest subproblem that is easy to solve , In the stage that has been solved by these + Calculation rules , You can directly find the second n Phase solution . So the meaning of initialization is , Find the solution in the initial stage .

3. The boundary conditions

The general topic will say what the boundary is , It can be understood as how to judge that all subproblems have been solved . Normal people can't write while（true） Well , You have to let the program end , Judge that you have solved this problem .

Four 、 The basic steps of dynamic programming

step1 decompose ：

Decompose a problem into multiple subproblems , Attention should be paid to the solution of sub problems The order , We should first solve the easy to solve subproblem , And the subsequent stage can pass through the previous stage + The decision was .

step2 State shift ：

The law obtained through , Write the equation of state transition .

The first n Stage = current state + Decision making （ front n Two stage solutions and calculation rules ）

step3 Write code ：

Calculate the first stage , In the intermediate stage, the state is calculated through the state transition equation , Until the end of all phase calculations .

step4 Get the solution ：

End of all phase calculations , Through simple statistics , for example Max,Min Wait for the value of the traversal phase , Get the final solution .

5、 ... and 、 Classical problems

Better a good memory than a bad pen , There are some problems applicable to dynamic programming , Can help us continuously strengthen our problem-solving ideas . When solving problems , I hope you can pay attention to the solution of the problem , See if it conforms to the four characteristics of dynamic programming , This continues to strengthen , To master the algorithm .

（1） Longest text substring

theory + practice , Take you to master dynamic programming _ Dynamic programming

Attached below is my explanation ：

https://leetcode-cn.com/problems/longest-palindromic-substring/solution/dong-tai-gui-hua-fa-qiu-jie-kan-bu-dong-octkt/

       
       // Dynamic programming has two basic elements ： Optimal substructure property and subproblem overlap property .
       
       // Many answers write initialization and boundary conditions , Personally, I think you should distinguish what his purpose is .
       
       // Many initialization and boundary conditions , Because the state transition equation , Is the solution of the subproblem that needs to be initialized , To avoid double counting , To put it bluntly, it is still a sub problem overlap and optimal sub structure problem .
       
       // We should pay attention to the decomposition of overlapping subproblems of a problem and the decision analysis of state optimization .
       
       // Their thinking :
       
       // When calculating a string ,  If it has the same beginning and end characters , Is it a palindrome , It depends on whether the string after removing the head and tail is a palindrome string .
       
       //  If its first and last characters are not equal , Then it must not be a palindrome 
       
       //leetcode submit region begin(Prohibit modification and deletion)
       
       class 
       
       Solution {
       
       public 
       
       String 
       
       longestPalindrome(
       
       String 
       
       s) {
       
       int 
       
       len 
       
       = 
       
       s.
       
       length();
       
       //  Special judgement 
       
       if (
       
       len 
       
       < 
       
       2){
       
       return 
       
       s;
       
        }
       
       int 
       
       maxLen 
       
       = 
       
       1;
       
       int 
       
       begin  
       
       = 
       
       0;
       
       // 1.  State definition 
       
       // dp[i][j]  Express s[i...j]  Is it a palindrome string , Now it means all 0, It's not a palindrome string 
       
       boolean[][] 
       
       dp 
       
       = 
       
       new 
       
       boolean[
       
       len][
       
       len];
       
       char[] 
       
       chars 
       
       = 
       
       s.
       
       toCharArray();
       
       // 2.  Calculation order of subproblems ： First calculate the short string , Calculating long strings , At the same time, according to the obtained short string or calculation rules , You can get the solution of a long string .
       
       //  Be careful ：s Indicates the element order of the calculation .
       
       // 0 1 2 3 4
       
       // 0 xx s1 s2 s4 s7
       
       // 1 xx s3 s5 s8
       
       // 2 xx s6 s9
       
       // 3 xx s10
       
       // 4 xx
       
       //  Why do you write that , Because you have to make sure that when you calculate an element , Through the state transition equation, we can get the dp[][].
       
       //  Rules for filling in the form ： Fill in one column first , Fill in line by line , Ensure that when calculating an element , The upper left cell has been calculated 
       
       //  Rules for filling in the form ： One line from left to right, of course , This also ensures that when calculating an element , The upper left cell has been calculated 
       
       for (
       
       int 
       
       j 
       
       = 
       
       1;
       
       j 
       
       < 
       
       len;
       
       j
       
       ++){
       
       for (
       
       int 
       
       i 
       
       = 
       
       0; 
       
       i 
       
       < 
       
       j; 
       
       i
       
       ++) {
       
       //  The beginning and end characters are not equal , It's not a palindrome string 
       
       if (
       
       chars[
       
       i] 
       
       != 
       
       chars[
       
       j]){
       
       dp[
       
       i][
       
       j] 
       
       = 
       
       false;
       
                }
       
       else {
       
       //  In the case of equality 
       
       //  Because there are no characters left after the head and tail are removed , Or when there is one character left , It must be a palindrome string 
       
       if (
       
       j 
       
       - 
       
       i 
       
       -
       
       1 
       
       <= 
       
       1){
       
       dp[
       
       i][
       
       j] 
       
       = 
       
       true;
       
                    }
       
       else {
       
       //  Equal head and tail , There is more than in the middle 1 Elements , This is the time , We can't directly judge whether he is a palindrome , But we can judge by the state transition equation 
       
       //  In fact, this is calculating s8 This element is , We can't judge dp[1][4] stay 1 and 4 When the bit elements are equal , Whether the whole string is a palindrome .
       
       //  So we have to go through s4 To judge ,s4 It's palindrome. ,s8 Namely .s4 No , that s8 It's not .
       
       dp[
       
       i][
       
       j] 
       
       = 
       
       dp[
       
       i 
       
       + 
       
       1][
       
       j 
       
       - 
       
       1];
       
                    }
       
                }
       
       //  as long as dp[i][j] == true  establish , Express s[i...j]  Is it a palindrome string 
       
       //  At this time, the record palindrome length and starting position are updated 
       
       if (
       
       dp[
       
       i][
       
       j] 
       
       && (
       
       j 
       
       - 
       
       i 
       
       + 
       
       1 
       
       > 
       
       maxLen)){
       
       maxLen 
       
       = 
       
       j 
       
       - 
       
       i 
       
       + 
       
       1;
       
       begin 
       
       = 
       
       i;
       
                }
       
            }
       
        }
       
       // 3.  initialization  
       
       //  Many answers write this , This step , Let's think about , In fact, there is no need .
       
       //  Because the main diagonal , The value can be judged directly .
       
       //  And in the process of solving , Our state transition equation will not use this value . Because only the main diagonal will use these values .
       
       //  And the subproblem solution of a single element , We don't need .
       
       //  therefore , Even if I put this initialization after the calculation , Even directly remove , It doesn't affect the result at all . You can try it on your own 
       
       // for (int i = 0; i < len; i++) {
       
       // dp[i][i] = true;
       
       // }
       
       // 4.  Return value 
       
       return 
       
       s.
       
       substring(
       
       begin,
       
       begin 
       
       + 
       
       maxLen);
       
    }
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.