Record path

Since we mentioned last time that we can pass ** Memory search as well as Dynamic programming and tabulation ** Get its length , But the curious thing is , Can we use some simple means , Record its path ？？
The answer, of course, is Sure Of , We just need one An array of the same size Can satisfy our little wish .
Action is better than action ~~~ Please look at the code. ：

Memory search

int process(string& str1, string& str2, int i, int j) {
    // With i,j Subscript for the end 
  if (dp[i][j])// If the answer to this position has been solved , Then return directly to the answer 
  {
    
    return dp[i][j];
  }
  if (i == 0 && j == 0) {
    // Analyze various boundary conditions （ When one or both strings have only one character left , Analyze the equality and inequality of the two ）, Find recursive exit 
    if (str1[i] == str2[j]) {
    
      dp[i][j] = 1;
    }
    flag[i][j] = 1;// Record path （ If they are the same, mark them as 1, Because there is only one character left in both strings ,
      // So whether it's marked as 1,2, still 3（ That is, wherever you go ） It's going to end , So it's not important to mark the number here ）
    return dp[i][j];
  }
  else if (i == 0) {
    
    if (str1[i] == str2[j]) {
    
      dp[i][j] = 1;
      flag[i][j] = 1;
      return dp[i][j];
    }
    else {
    // If different , Then marked as 2（ Go to the left ）
      dp[i][j] = process(str1, str2, i, j - 1); flag[i][j] = 2; return dp[i][j];
    }
  }
  else if (j == 0) {
    
    if (str1[i] == str2[j]) {
    
      flag[i][j] = 1;

      dp[i][j] = 1; return dp[i][j];
    }
    else {
    // Marked as 3（ Go to the right ）
      dp[i][j] = process(str1, str2, i - 1, j); flag[i][j] = 3; return dp[i][j];
    }
  }

  int p1 = process(str1, str2, i, j - 1);
  int p2 = process(str1, str2, i - 1, j); int p3 = 0;
  if (str1[i] == str2[j]) {
    
    p3 = process(str1, str2, i - 1, j - 1) + 1;
    flag[i][j] = 1;// If they are equal, mark 
  }
  dp[i][j] = max(max(p1, p2), p3);
  if (!flag[i][j]) {
    // If it works here , That means it wasn't marked before , That is, the two characters are not equal , Then find the mark with the largest length in the next step 
    if (p2 >= p1)flag[i][j] = 3;
    else flag[i][j] = 2;
  }
  return dp[i][j];
}

So let's say , We just need to define one flag The array can record the path , So how to output ？ Please have a look at FindPath function

void FindPath(int i, int j, string& text1, string& text2) {
    
  if (i < 0 || j < 0)return;
  if (flag[i][j] == 1) {
    
    FindPath(i - 1, j - 1, text1, text2);
    cout << text1[i];//text2[j]
  }
  else if (flag[i][j] == 2)
  {
    
    FindPath(i, j - 1, text1, text2);
  }
  else
  {
    
    FindPath(i - 1, j, text1, text2);
  }
}

The main function says ：

int longestCommonSubsequence(string text1, string text2) {
    
  dp.resize(text1.size(), vector<int>(text2.size())); flag.resize(text1.size(), vector<int>(text2.size()));
  string path = "";
  int ana = process(text1, text2, text1.size() - 1, text2.size() - 1);
  FindPath(text1.size() - 1, text2.size() - 1, text1, text2);
  return ana;
}
int main() {
    
  cout << longestCommonSubsequence("YiQingTuiSan", "YIQINGTUISAN") << endl;
  for (vector<int>t : flag) {
    
    for (int i : t)cout << i << " ";
    cout << endl;
  }
  return 0;
}

see ！ That's the charm of recursion , We just need to define the conditions , Leave the rest to recursion, hahaha

Cough , Return to the right topic …
Now that we know how to write a memory search version , Then dynamic programming is easy to catch …

Dynamic programming

Note that there i And j from 1 Start , Because we put the boundary of the above memorized search into the loop , So add one more layer on both sides

void LCS()
{
    
    for(int i = 1; i <= len1; i++){
    
        for(int j = 1; j <= len2; j++){
    
            if(s1[i-1] == s2[j-1]){
     // notes ： Here s1 And s2 The sequence is from s1[0] And s2[0] At the beginning 
                c[i][j] = c[i-1][j-1] + 1;
                b[i][j] = 1;// Mark each situation , It is convenient to enter the path later  
            }
            else{
     //c[i][j] = max(c[i][j-1], c[i-1][j]) 
                if(c[i][j-1] >= c[i-1][j]){
    
                    c[i][j] = c[i][j-1];
                    b[i][j] = 2; // The second case  
                }
                else{
    
                    c[i][j] = c[i-1][j];
                    b[i][j] =3; // The third case  
                }
            }
        }
    }
}

So should our output function also adapt to local conditions ？

void FindPath(int i, int j, string& text1, string& text2) {
    
  if (i == 0 || j == 0)return;// It's different here , Remember the length of the upper pass 
  if (flag[i][j] == 1) {
    
    FindPath(i - 1, j - 1, text1, text2);
    cout << text1[i];//text2[j]
  }
  else if (flag[i][j] == 2)
  {
    
    FindPath(i, j - 1, text1, text2);
  }
  else
  {
    
    FindPath(i - 1, j, text1, text2);
  }
}