Theory + practice will help you master the dynamic programming method

Abstract ：

This paper introduces the basic concept of dynamic programming method , By analyzing the characteristics of dynamic programming method in detail , Give the idea of judging whether the problem is solved by dynamic programming .

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 .

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 ~