记录路径

既然上回讲到我们可以通过**记忆化搜索以及动态规划打表**得到其长度，但令人好奇的是，我们是否可以通过一些简单的手段，将其路径记录下来呢？？
答案当然是可以的，我们只需要借助一个同等大小的数组便可以满足我们这小小的心愿。
心动不如行动~~~请看代码：

记忆化搜索

int process(string& str1, string& str2, int i, int j) {
    //以i，j为结尾下标
  if (dp[i][j])//如果该位置的答案已经被求解出来，那么直接返回答案
  {
    
    return dp[i][j];
  }
  if (i == 0 && j == 0) {
    //分析各种边界条件（当两字符串其中一个或者都只剩下一个字符时，分析两者相等与不等的情况），找递归出口
    if (str1[i] == str2[j]) {
    
      dp[i][j] = 1;
    }
    flag[i][j] = 1;//记录路径（如果相同就标为1，而因为这里两个字符串都只剩下一个字符，
      //所以无论标为1,2,还是3（即无论向哪走）都会结束，所以这里标几也就不重要了）
    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 {
    //如果不同，则标为2（往左走）
      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 {
    //标为3（往右走）
      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;//如果相等就先标上
  }
  dp[i][j] = max(max(p1, p2), p3);
  if (!flag[i][j]) {
    //这里如果成立，这说明之前没标上，也就是两个字符不相等，那么就找下一步长度最大的标上
    if (p2 >= p1)flag[i][j] = 3;
    else flag[i][j] = 2;
  }
  return dp[i][j];
}

所以说呢，我们只需要定义一个flag数组便可以记录下来路径，那么如何去输出呢？请看FindPath函数

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);
  }
}

主函数如是说：

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;
}

看！这就是递归的魅力，我们只需要定义一下条件，剩下的交给递归哈哈哈

咳咳，回归正题…
既然我们已经知道了如何去写记忆化搜索版本，那么动态规划也是手到擒来啦…

动态规划

注意这里i与j都是从1开始，因为我们将上述记忆化搜索的边界也一块写进循环里去了，所以要两边多加一层

void LCS()
{
    
    for(int i = 1; i <= len1; i++){
    
        for(int j = 1; j <= len2; j++){
    
            if(s1[i-1] == s2[j-1]){
     //注：此处的s1与s2序列是从s1[0]与s2[0]开始的
                c[i][j] = c[i-1][j-1] + 1;
                b[i][j] = 1;//给每种情况打标记，后面方便输入路径 
            }
            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; //第二种情况 
                }
                else{
    
                    c[i][j] = c[i-1][j];
                    b[i][j] =3; //第三种情况 
                }
            }
        }
    }
}

那么我们的输出函数是不是也该因地制宜呢？

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);
  }
}