从递归到动态规划（三）最长公共子序列

以前看到这种问题的时候，觉得这种问题还是挺无聊的，虽然做出来后自己会听激动的，但很多时候不知道这有什么用。今天看到《算法导论》那里提到这个用来搞两条 DNA 的比较，顿时就觉得这种问题还是挺有意思。

问题是这样的，有一个 DNA s1 是 "ACCGG" ，另一条 DNA s2 是 "GTCGT"，求最大的公共子序列，可以不连续的。

。。。

先思考一下。

暴力遍历

首先，想到的解决方法一般都是暴力破解的。先求出所有 s1 的所有子序列，再求出 s2 的所有子序列。然后通过对比最后获得最长的公共子序列。

当然这时间复杂度也是挺感人的，假如 s1 的长度是 m，s2 的长度是 n。用类似 2 进制可以表示所有数的思想，可知求出 s1 的所有子序列的复杂读是 O(2^m)，可求出 s2 的所有子序列的复杂度是 O(2^n),而遍历对比的复杂度是 O(2^m*n)

...

这复杂度太难以接受了。。。

递归

如果是树形递归的思想呢？

树形递归的思想是这样的，假如 s1[0:i-1] 与 s2[0:j-1] 之间有一条最长的公共子序列 seq 如果 s1[i] == s2[j] ，那么最长公共子序列就是 seq + s1[i] 如果不相等，最长公共子序列就是 LCS(s1[0:i]，s2[0:j-1]) 或者是 LSC(s1[0:i-1], s2[0:j]) 中取最长。那么是什么时候结束呢？应该是 i < 0 或者 j < 0 吧。

所以如果用递归很容易写出这样的代码


string lcs(string s1, string s2, int i, int j) {
  if (i < 0 || j < 0)
    return "";
  else if (s1[i] == s2[j])
    return lcs(s1, s2, i - 1, j - 1) + s1[i];
  else {
    string p1 = lcs(s1, s2, i - 1, j);
    string p2 = lcs(s1, s2, i, j - 1);
    if (p1.length() > p2.length()) {
      return p1;
    }
    return p2;
  }
}
 
string lcs(string s1, string s2) {
  return lcs(s1, s2, s1.length() - 1, s2.length() - 1);
}
复制代码

这当然是一如既往的有重复计算的问题的。如果用动态规划的思想。大概会是这样。

就比较容易写出这样的代码。


int lcs2(string s1, string s2) {
  int m = s1.length();
  int n = s2.length();
 
  vector<vector<int>> c(m + 1, vector<int>(n + 1));
 
  for (int i = 0; i < m + 1; i++) {
    for (int j = 0; j < n + 1; j++) {
      if (i == 0 || j == 0)
        c[i][j] = 0;
      //算法导论字符串是从1开始的，所以这里要减一
      //也方便后续的操作
      else if (s1[i - 1] == s2[j - 1])
        c[i][j] = c[i - 1][j - 1] + 1 ;
      else
        c[i][j] = max(c[i - 1][j], c[i][j - 1]);
    }
  }
  return c[m][n];
}
复制代码

但是这样的操作只能说求出了最长公共子序列的长度。并没有将序列求出来了。求出序列简单，按照原来的思路再遍历一次就可以了

从底向上遍历如果 s1[m-1] == s2[n-1] 就说明 c[m]][n] 是最长自序列的一个元素，否则就根据大小决定是向左还是向上走。


string res = "";
int i = m;
int j = n;
    
while (i > 0 && j > 0) {
    if (s1[i - 1] == s2[j - 1]) {
        res = s1[i - 1] + res;
        j--;
        i--;
    } else if(c[i-1][j] > s2[i][j-1]){
        i--;
    }else {
        j--;
    }
}
return res;
复制代码

自顶向下遍历。

如果 s1[i-1] == s2[j-1] 就说明最长自序列的一个元素，就 i++,j++ ，向右下角走。否则对比右边和下边哪边打就走哪边。


string res = "";
int i = 1;
int j = 1;
 
while (i < m && j < n) {
    if (s1[i - 1] == s2[j - 1]) {
        res = res + s1[i - 1];
        j++;
        i++;
    } else if (c[i + 1][j] >= c[i][j + 1]) {
         i++;
    } else {
        j++;
    }
  }
 
 return res;
复制代码