-----------
This article will tell you two questions ：
1、 What on earth is 「 Optimal substructure 」, What does it have to do with dynamic planning .
2、 Why do dynamic programming traverse dp Arrays come in a variety of ways , Some are traversing , Some traverse backwards , Some traverse sideways .
One 、 The optimal substructure is explained in detail
「 Optimal substructure 」 A certain nature of a problem , It's not a dynamic programming problem . in other words , Many problems actually have optimal substructures , It's just that most of them don't have overlapping subproblems , So we don't classify them as dynamic programming problems .
Let me start with an easy to understand example ： Suppose your school has 10 A class , You've worked out the highest exam score for each class . Now I ask you to calculate the highest grade in the whole school , Can you count ？ Of course. , And you don't have to go through the whole school and compare scores , It's just here 10 One of the highest scores is the highest in the whole school .
The question I put to you is In accordance with the optimal substructure ： From the optimal result of the subproblem, we can deduce the optimal result of a larger scale problem . It's up to you Every class The best result is the subproblem , When you know the answers to all the sub questions , You can use this to launch School The answer to the larger question of students' best grades .
You see , Such a simple problem has the property of optimal substructure , It's just because there's no overlap problem , So we can't use dynamic programming simply to find the maximum value .
Another example ： Suppose your school has 10 A class , You know the maximum score difference for each class （ The difference between the highest score and the lowest score ）. So now I'll ask you to calculate the maximum score difference among all the students in the school , Can you count ？ You can figure it out , But certainly not through the known 10 The maximum score difference of each class is calculated . Because of this 10 The maximum score difference of a class does not necessarily include the maximum score difference of the whole school students , For example, the maximum score difference of the whole school may be 3 The highest score of the class and 6 The lowest score difference in the class .
The question I'm going to ask you this time is Not in line with the optimal substructure , Because you didn't get the best value of the whole school through the optimal value of each class , There is no way to deduce the optimal value of a larger problem through the optimal value of the subproblem . above 「 Dynamic planning details 」 Said , We want to satisfy the optimal subjunctions , Subproblems must be independent of each other . The school's maximum score difference may be between two classes , Obviously, subproblems are not independent , So the problem itself does not conform to the optimal substructure .
Then, in the case of this optimal substructure failure , What do I do ？ Strategy is ： Transformation problem . For the problem of maximum score difference , Isn't it impossible for us to make use of the known score difference of each class , Then I can only write a violent code like this ：
int result = 0;
for (Student a : school) {
for (Student b : school) {
if (a is b) continue;
result = max(result, |a.score - b.score|);
}
}
return result;
Transformation problem , In other words, the problem is equivalent to the transformation ： Maximum score difference , It's equivalent to the difference between the highest score and the lowest score , That is to ask for the highest and lowest scores , Isn't that the first question we discussed , It has the optimal substructure ？ Now change your mind , Solving the maximum value problem with the help of optimal substructure , Go back and solve the maximum score difference problem , Is it more efficient ？
Of course , The above example is too simple , But let's look back , We do dynamic programming , Have you been looking for the best value , The essence is no different from our example , We need to deal with the overlap problem .
No The same definition, different solutions It shows how to transform the problem , Different optimal substructures , May lead to different solutions and efficiencies .
PS： I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating . Recommended collection , Write the title in the order of my article , Master all kinds of algorithm set, then put into the sea of questions, like fish .
Another common but very simple example , Find the maximum of a binary tree , It's not hard （ Simplicity , Suppose that the values in the node are nonnegative ）：
int maxVal(TreeNode root) {
if (root == null)
return -1;
int left = maxVal(root.left);
int right = maxVal(root.right);
return max(root.val, left, right);
}
You see, this problem also conforms to the optimal substructure , With root Is the maximum value of the root tree , You can go through the subtrees on both sides （ Sub problem ） The maximum value of is derived , Combine the example of school and class just now , It's easy to understand .
Of course, this is not a dynamic programming problem , It is intended to illustrate , Optimal substructure is not a unique property of dynamic programming , Most of the problems that can find the maximum value have this property ; But, in turn, , The optimal substructure property is a necessary condition for dynamic programming problems , It must be the best value for you , Later, I came across the most valuable question of disgusting people , It's right to think about dynamic planning , This is the routine .
Dynamic programming is not from the simplest base case Can we deduce it later , Think of it as a chain reaction , throw a sprat to catch a herring . But there are only problems that conform to the optimal substructure , It's the nature of this chain reaction .
The process of finding the optimal substructure , In fact, it is the process of proving the correctness of the state transition equation , If the equation satisfies the optimal substructure, the violent solution can be written , Write a violent solution to see if there is an overlap problem , If there is, optimize , No rules OK. It's a routine , Friends who often brush questions should be able to understand .
I'm not going to give you any real examples of dynamic programming , Readers can turn to historical articles , See how the state transition follows the optimal substructure , That's all for the topic , Let's look at another dynamic programming puzzle behavior .
Two 、dp The traversal direction of the array
I believe that when readers do dynamic programming problems , It must be right dp Array traversal order is a bit of a headache . Let's take two dimensions dp Array to illustrate , Sometimes we're forward traversing ：
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
// Calculation dp[i][j]
Sometimes we traverse backwards ：
for (int i = m - 1; i >= 0; i--)
for (int j = n - 1; j >= 0; j--)
// Calculation dp[i][j]
Sometimes it's possible to traverse diagonally ：
// Traversing the array diagonally
for (int l = 2; l <= n; l++) {
for (int i = 0; i <= n - l; i++) {
int j = l + i - 1;
// Calculation dp[i][j]
}
}
Even more confusing is , Sometimes it is found that both forward and backward traversal can get the correct answer , Let's say we have 「 The problem of mass destruction of stocks 」 In some places, it can be both positive and negative .
that , If you look closely, you can find out why . You just have to hold on to two ：
1、 During traversal , The required state must be calculated .
2、 The end of the traversal must be the location where the results are stored .
Let's explain what the above two principles mean .
For example, the classic problem of editing distance , For a detailed explanation, please refer to the previous article 「 Edit distance to explain 」, We pass the right dp Definition of array , To determine the base case yes dp[..][0] and dp[0][..], The final answer is dp[m][n]; And we know from the state transition equation that dp[i][j] Need from dp[i-1][j], dp[i][j-1], dp[i-1][j-1] Transfer from , Here's the picture ：
that , Refer to the two principles just mentioned , How do you traverse dp Array ？ It must be forward traversal ：
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
// adopt dp[i-1][j], dp[i][j - 1], dp[i-1][j-1]
// Calculation dp[i][j]
because , So the left side of each iteration 、 above 、 The top left position is base case Or what we've calculated before , And it ends up with the answer we want dp[m][n].
Take another example , Palindrome subsequence problem , See previous 「 Subsequence problem template 」, We've been through to dp Definition of array , To determine the base case The diagonal in the middle ,dp[i][j] Need from dp[i+1][j], dp[i][j-1], dp[i+1][j-1] Transfer from , The final answer you want to ask for is dp[0][n-1], Here's the picture ：
This situation is based on the two principles , There are two ways to traverse correctly ：
Or traverse it sideways from left to right , Or from bottom to top, from left to right , So that we can make sure that every time dp[i][j] Left side 、 Underside 、 The bottom left has been calculated , Get the right results .
Now? , You should understand these two principles , The main thing is to see base case And where the final results are stored , Ensure that the data used in the traversal process is calculated , Sometimes there are many ways to get the right answer , You can choose according to your taste .
＿＿＿＿＿＿＿＿＿＿＿＿＿
my Online e-books Yes 100 Original articles , Hands with brushes 200 Daoli is the subject , Recommended collection ！ Corresponding GitHub Algorithm Repository We've got it 70k star, Welcome to mark star ！
