当前位置:网站首页>Dynamic planning

Dynamic planning

2020-11-08 19:51:20 labuladong,

-----------

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 !

版权声明
本文为[labuladong,]所创,转载请带上原文链接,感谢