Theory + practice will help you master the dynamic programming method

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

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);
    }
}

Click to follow , The first time to learn about Huawei's new cloud technology ~​