# State compression: dimension reduction of dynamic programming

2020-11-07 21:04:14

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[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 == s`, So now you'll go into the logic below, right ：

``````if (s == s)
// dp = dp[i+1][j-1] + 2;
dp = 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`, But this is the outer layer for The last iteration of the loop corresponds to `dp`, That's two dimensions `dp` Array `dp[i+1] = dp`.

in other words ,`pre` The variable is `dp[i+1][j-1] = dp`, 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 ！