当前位置:网站首页>State compression: dimension reduction of dynamic programming

State compression: dimension reduction of dynamic programming

2020-11-07 21:04:14 labuladong,

We wrote dozens of dynamic planning articles before the number , It can be said that dynamic programming techniques are very significant for the improvement of algorithm efficiency , Generally speaking, the algorithm of time complexity of exponential level and factorial level can be optimized to O(N^2), It can be called the two-way foil in the field of algorithm , All kinds of ghosts and monsters are broken into two dimensions .

however , Dynamic planning itself can also be optimized in stages , For example, we often hear that 「 State compression 」 skill , It can reduce the space complexity of many dynamic programming solutions , from O(N^2) Down to O(N),

Dynamic programming that can use state compression techniques is two-dimensional dp problem , You look at its state transition equation , If the computing state dp[i][j] All that is needed is dp[i][j] The state of adjacency , Then you can use the state compression technique , Two dimensional dp The array is converted into one dimension , Change the spatial complexity from O(N^2) Down to O(N).

What do you mean 「 and dp[i][j] The state of adjacency 」 Well , For example The longest palindrome subsequence in , The final code is as follows :

int longestPalindromeSubseq(string s) {
    int n = s.size();
    // dp  The array is all initialized to  0
    vector<vector<int>> dp(n, vector<int>(n, 0));
    // base case
    for (int i = 0; i < n; i++)
        dp[i][i] = 1;
    //  Reverse traversal ensures correct state transition 
    for (int i = n - 2; i >= 0; i--) {
        for (int j = i + 1; j < n; j++) {
            //  State transition equation 
            if (s[i] == s[j])
                dp[i][j] = dp[i + 1][j - 1] + 2;
            else
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
        }
    }
    //  Whole  s  The longest palindrome substring length of 
    return dp[0][n - 1];
}

PS: We don't discuss how to push the state transfer equation , Only two dimensions are discussed DP Problem state compression techniques . All of them are general skills , So if you haven't read the previous article , It doesn't matter if you don't understand the logic of this code , You don't learn to compress completely .

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 .

You see, we are right about dp[i][j] Update , In fact, it only depends on dp[i+1][j-1], dp[i][j-1], dp[i+1][j] These three states :

This is called and dp[i][j] adjacent , Anyway, you calculate dp[i][j] Just the three adjacent states , Actually, it doesn't need to be so big and two-dimensional dp table Isn't it ? The core idea of state compression is , Put two-dimensional array 「 Projection 」 To a one-dimensional array

The idea is very intuitive , But there is an obvious problem , In the figure dp[i][j-1] and dp[i+1][j-1] These two states are in the same column , One dimensional array can only hold one , So when I calculate dp[i][j] when , One of them will be covered by the other , What do I do ?

This is the difficulty of state compression , The following is to analyze and solve this problem , Or take 「 The longest palindrome subsequence 」 Problem distance , The main logic of its state transfer equation is the following code :

for (int i = n - 2; i >= 0; i--) {
    for (int j = i + 1; j < n; j++) {
        //  State transition equation 
        if (s[i] == s[j])
            dp[i][j] = dp[i + 1][j - 1] + 2;
        else
            dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
    }
}

I want to put two dimensions dp The array is compressed into one dimension , Generally speaking, the first dimension , That is to say i Remove this dimension , only j This dimension . One dimension after compression dp The array is the previous two dimensions dp Array of dp[i][..] That line .

Let's modify the above code first , Directly without brain i This dimension , hold dp The array becomes one-dimensional :

for (int i = n - 2; i >= 0; i--) {
    for (int j = i + 1; j < n; j++) {
        //  ad locum , A one-dimensional  dp  What are the numbers in the array ?
        if (s[i] == s[j])
            dp[j] = dp[j - 1] + 2;
        else
            dp[j] = max(dp[j], dp[j - 1]);
    }
}

One dimension of the above code dp Arrays can only represent two dimensions dp A row in an array dp[i][..], Then how can I get dp[i+1][j-1], dp[i][j-1], dp[i+1][j] These necessary values , How about state transition ?

The location of comments in the code , There will be a state transition , to update dp[j], So we have two questions to think about :

1、 In the face of dp[j] Before assigning new values ,dp[j] It corresponds to two dimensions dp Where in the array ?

2、dp[j-1] It corresponds to two dimensions dp Where in the array ?

For questions 1, In the face of dp[j] Before assigning new values ,dp[j] The value of is the outer layer for Loop the value from the last iteration , That is, it corresponds to two dimensions dp Array dp[i+1][j] The location of .

For questions 2,dp[j-1] The value of is the inner layer for Loop the value from the last iteration , That is, it corresponds to two dimensions dp Array dp[i][j-1] The location of .

Half of the problem has been solved , There's only two dimensions left dp Array dp[i+1][j-1] We can't go directly from one dimension to this state dp In the array :

for (int i = n - 2; i >= 0; i--) {
    for (int j = i + 1; j < n; j++) {
        if (s[i] == s[j])
            // dp[i][j] = dp[i+1][j-1] + 2;
            dp[j] = ?? + 2;
        else
            // dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
            dp[j] = max(dp[j], dp[j - 1]);
    }
}

because for Loop traversal i and j From left to right , From the bottom up , So we can find that , In updating one dimension dp When you have an array ,dp[i+1][j-1] Will be dp[i][j-1] overwrite , The diagram shows the order in which these four positions are traversed :

So if we want to get dp[i+1][j-1], You have to use a temporary variable before it is covered temp Save it , And keep the value of this variable until the calculation dp[i][j] When . In order to achieve this goal , Combining with the above , We can write code like this :

for (int i = n - 2; i >= 0; i--) {
    //  Storage  dp[i+1][j-1]  The variable of 
    int pre = 0;
    for (int j = i + 1; j < n; j++) {
        int temp = dp[j];
        if (s[i] == s[j])
            // dp[i][j] = dp[i+1][j-1] + 2;
            dp[j] = pre + 2;
        else
            dp[j] = max(dp[j], dp[j - 1]);
        //  To the next cycle ,pre  Namely  dp[i+1][j-1]  了 
        pre = temp;
    }
}

Don't underestimate this code , It's one-dimensional dp The best part , It's not difficult to meet. , The hard ones will not. . For the sake of clarity , I'm going to take this logic apart with concrete values :

Suppose now i = 5, j = 7 And s[5] == s[7], So now you'll go into the logic below, right :

if (s[5] == s[7])
    // dp[5][7] = dp[i+1][j-1] + 2;
    dp[7] = pre + 2;

I ask you this pre What is a variable ? It's the inner layer for Loop the last iteration of temp value .

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 .

Then I'll ask you the inner layer for Loop the last iteration of temp What is the value ? yes dp[j-1] That is to say dp[6], But this is the outer layer for The last iteration of the loop corresponds to dp[6], That's two dimensions dp Array dp[i+1][6] = dp[6][6].

in other words ,pre The variable is dp[i+1][j-1] = dp[6][6], That's what we want .

So now we have successfully reduced the dimension of state transfer equation , It's the toughest bone you've ever had , But notice that we still have base case We have to deal with it :

// dp  The array is all initialized to  0
vector<vector<int>> dp(n, vector<int>(n, 0));
// base case
for (int i = 0; i < n; i++)
    dp[i][i] = 1;

How to make base case It's also one-dimensional ? It's simple , Remember that state compression is projection , We put base case Project it to one dimension and see :

A two-dimensional dp Array base case All fall into one dimension dp Array , There is no conflict and coverage , So it's just like we write code like this :

//  A one-dimensional  dp  The array is all initialized to  1
vector<int> dp(n, 1);

thus , We put base case And the state transition equation are reduced , Actually, the complete code has been written :

int longestPalindromeSubseq(string s) {
    int n = s.size();
    // base case: A one-dimensional  dp  The array is all initialized to  0
    vector<int> dp(n, 1);

    for (int i = n - 2; i >= 0; i--) {
        int pre = 0;
        for (int j = i + 1; j < n; j++) {
            int temp = dp[j];
            //  State transition equation 
            if (s[i] == s[j])
                dp[j] = pre + 2;
            else
                dp[j] = max(dp[j], dp[j - 1]);
            pre = temp;
        }
    }
    return dp[n - 1];
}

This is the end of the article , But the state compression technique is more powerful , It is also based on the conventional dynamic planning ideas .

You see, too , Using the state compression technique for two-dimensional dp After the array dimension reduction attack , The readability of the solution code becomes very poor , If you look directly at this solution , Everyone has a confused face . The optimization of the algorithm is such a process , Write a very readable recursive algorithm for violence first , Then try to optimize the overlapping sub problem with dynamic programming technique , Finally, we try to optimize the space complexity with state compression technique .

in other words , You can at least be proficient in using our previous article Dynamic planning framework is explained in detail Find the state transition equation , Write a correct dynamic programming solution , Then it is possible to observe the state shift , Analyze whether state compression techniques can be used to optimize .

I hope readers can be steady , Step by step , For this optimization of comparative limits , Don't do it . After all, the routine is in the heart , I'm not afraid of anything in the world !

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