We have written more than a dozen dynamic programming articles before, and it can be said that dynamic programming techniques can improve the efficiency of algorithms very significantly. Generally speaking, they can optimize the exponential and factorial time complexity algorithms into O(N^2), which can be called the binary foil of the algorithm world, and make the various monsters into quadratic elements.

However, dynamic programming itself can also be phased optimized. For example, we often hear about the “state compression” technique, which can further reduce the spatial complexity of many dynamic programming solutions from O(N^2) to O(N).

The dynamic programming that can use the state compression technique is all two-dimensional DP problems. If you look at the state transition equation, if all the states needed to compute the state DP [I][j] are adjacent to the state DP [I][j], then you can use the state compression technique to convert the two-dimensional DP array into one dimension. Reduce the space complexity from O(N^2) to O(N).

(dp[I][j]) (dp[I][j]) (dp[I][j]

int longestPalindromeSubseq(string s) {
    int n = s.size(a);// all dp arrays are 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;
    // Iterate backwards to ensure correct state transitions
    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]); }}// The longest substring length of the entire s
    return dp[0][n - 1];
}
Copy the code

PS: In this paper, we do not discuss how to deduce the state transition equation, but only discuss the technique of state compression for the two-dimensional DP problem. The techniques are universal, so if you haven’t read the previous section and don’t understand the logic of this code, it won’t stop you from learning state compression.

PS: I have carefully written more than 100 original articles and brushed 200 force button topics hand by hand, all of which were published in labuladong’s algorithm cheat sheet and updated continuously. Suggested collection, in accordance with the order of my article brush topic, master all kinds of algorithm set to re-enter the sea of questions like a duck in water.

Do you think we update of dp [I] [j], really only depends on the dp + 1] [I] [j – 1, dp [1], [I] dp [j] [I + 1] these three states:

Dp [I][j] = dp[I][j] = dp[I][j] = dp[I][j] = DP [I] The idea behind state compression is to “project” a two-dimensional array onto a one-dimensional array:

In the figure, dp[I][j-1] and DP [I +1][J-1] are in the same column, and there is only room for one in the one-dimensional array. Therefore, when I calculate DP [I][j], one of them must be covered by the other. What should I do?

This is the difficulty of state compression, and the following is to analyze and solve this problem, or to take the distance of the problem of “longest subroutine sequence”. The main logic of its state transition 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]); }}Copy the code

If you want to compress a two-dimensional DP array into one dimension, you generally remove the first dimension, the I dimension, leaving only the j dimension. The compressed one-dimensional DP array is the dp of the previous two-dimensional DP array [I][..]. The line.

Let’s modify the above code to remove the dimension I and make the dp array one-dimensional:

for (int i = n - 2; i >= 0; i--) {
    for (int j = i + 1; j < n; j++) {
        // In this case, what are the numbers in the one-dimensional dp array?
        if (s[i] == s[j])
            dp[j] = dp[j - 1] + 2;
        else
            dp[j] = max(dp[j], dp[j - 1]); }}Copy the code

The one-dimensional DP array of the above code can represent only one line of the two-dimensional DP array dp[I][.. , how can I get dp[I +1][j-1], dp[I][j-1], dp[I +1][j] the necessary values for state transition?

At the point in the code where the comment is going to be transferred to update dp[j], we need to think about two questions:

1, before assigning a new value to dp[j], what position in the two-dimensional DP array does dp[j] correspond to?

2. What position does DP [J-1] correspond to in the two-dimensional DP array?

For problem 1, before assigning a new value to dp[j], the value of dp[j] is the value calculated by the last iteration of the outer for loop, that is, the position of DP [I +1][j] in the corresponding two-dimensional DP array.

For problem 2, the value of dp[J-1] is the value calculated by the last iteration of the inner for loop, that is, the position of DP [I][J-1] in the corresponding two-dimensional DP array.

So the problem has been solved more than half, only the state dp[I +1][J-1] in the two-dimensional DP array is left, which we cannot directly obtain from the one-dimensional DP 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]); }}Copy the code

Because the sequence of for loop traversing I and j is from left to right and from bottom to top, it can be found that when updating the one-dimensional DP array, DP [I +1][J-1] will be overwritten by DP [I][J-1]. The sequence of traversing these four positions is marked in the figure:

So if we want dp[I +1][j-1], we must store it in a temporary variable temp before it is overwritten, and hold the value of this variable until we evaluate dp[I][j]. To do this, we can write code like this, combined with the figure above:

for (int i = n - 2; i >= 0; i--) {
    // Store variable dp[I +1][j-1]
    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]);
        // In the next loop, pre is dp[I +1][j-1]pre = temp; }}Copy the code

Don’t look down upon this code, this is one dimensional DP the most sophisticated place, will not be difficult, not. For clarity, I break down the logic with concrete numbers:

Suppose I = 5, j = 7, and s[5] == s[7], then the following logic will now enter, right:

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

I asked you what is this pre variable? Is the temp value of the last iteration of the inner for loop.

PS: I have carefully written more than 100 original articles and brushed 200 force button topics hand by hand, all of which were published in labuladong’s algorithm cheat sheet and updated continuously. Suggested collection, in accordance with the order of my article brush topic, master all kinds of algorithm set to re-enter the sea of questions like a duck in water.

What was the temp value of the last iteration of the inner for loop? Is DP [J-1], that is, DP [6], but this is dp[6] corresponding to the last iteration of the outer for loop, that is, DP [I +1][6] = DP [6][6] in the two-dimensional DP array.

In other words, the pre variable is dp[I +1][J-1] = dp[6][6], which is what we want.

So now we have successfully reduced the dimension of the state transition equation, which is the hardest bone to chew, but note that we still have base cases to deal with:

// all dp arrays are 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;
Copy the code

How do you make base case one-dimensional? Very simple, remember that state compression is a projection, let’s project the base case to one dimension:

All the base cases in the two-dimensional DP array fall into the one-dimensional DP array, so there is no conflict or overwrite, so we can write the code directly like this:

// One dimensional dp arrays are all initialized to 1
vector<int> dp(n, 1);
Copy the code

So far, we have reduced the dimensions of both the base case and the state transition equation, and we have actually written the complete code:

int longestPalindromeSubseq(string s) {
    int n = s.size(a);// base case: one dimensional dp arrays are 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];
}
Copy the code

That’s the end of this article, but the state compression technique, however awesome it is, is based on the general dynamic programming idea.

As you can see, the solution code becomes very unreadable after using the state compression technique to reduce the dimension of the TWO-DIMENSIONAL DP array, and if you look at this solution directly, anyone will be confused. Algorithm optimization is such a process, first write a violent recursive algorithm with good readability, then try to use dynamic programming skills to optimize overlapping subproblems, and finally try to use state compression skills to optimize spatial complexity.

In other words, you should at least be able to find the state transition equation and write a correct solution to the dynamic programming framework using the routines described above. Then it is possible to observe the state transition and analyze whether it is possible to optimize using state compression techniques.

I hope readers can play steadily, layer by layer, for the optimization of this comparison limit, do not make it worth while. After all, routine in the heart, all over the world are not afraid!