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 ！