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 !