题解 | #最长公共子序列-II#

本题是动态规划的一道典型题目，也被收录在《算法导论》中当做动态规划章节的学习例题，是非常重要的一道题，可以很好锻炼到动态规划的思路模式。

思路

题目分析

1. 题目给出了两个字符串，要求我们从这两个字符串中，找出最长的公共部分组成子串
2. 需要注意的是，最终的子串中的元素必须在两个初始字符串中都出现
3. 而且最终的子串中的数字前后相对位置和原来两个字符串中的前后相对位置一致
4. 我们最终的目的就是找到这样的子串

• 我们设定字符串s1的长度为m，s2的长度为n，用一个二维数组来作为动态规划dp数组。
  • 其中dp[i][j]表示字符串s1[0...i-1]和s2[0...j-1]的最长公共子序列的长度
  • dp[m][n]是我们要最终得到的最长公共子序列的最终长度
• 转移状态分析
  • 我们发现dp[i][j]的来源有三个方向：
    • 当s1[i-1] == s2[j-1]时，我们知道最长公共子序列的长度变长了，所以有dp[i][j]=dp[i-1][j-1]+1
    • 当s1[i-1] != s2[j-1]时，我们可以知道当前的两个字符串的末位不能延长目前的最长公共子序列，因此此时dp[i][j]取决于dp[i-1][j]和dp[i][j-1]
• 状态转移方程如下
  
• 这样我们可以得到最终的最长公共子序列的长度，并且在dp数组中保存了各个位置的最长公共子序列的长度。
• 在找到最终的最长公共子序列时，我们需要沿着dp数组从最终位置回调寻找。
  • 方法一通过另外部署路径的二维数组，沿着路线回调最长公共子序列。
  • 方法二通过dp数组根据值来选择回调出最长公共子序列。

方法一：动态规划（两个二维数组，超空间无法通过）

通过两个二维数组来记录必要的信息，思路更加清楚，一个len数组记录最长公共子序列长度的过程，一个path数组记录产生最长公共子序列的路径，便于最终产生子序列字符串。

class Solution {
public:
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    vector<vector<char>> LCS_path(string s1, string s2) {
        int m = s1.size();
        int n = s2.size();
        vector<vector<char>> path(m+1, vector<char>(n+1));       //path数组记录路径
        vector<vector<int>> len(m+1, vector<int>(n+1, 0));       //len数组记录长度
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(s1[i-1] == s2[j-1]) {                        //转移方程的第一种情况
                    len[i][j] = len[i-1][j-1] + 1;              //需要延长子序列长度
                    path[i][j] = 'q';                           //记录路径来自左上角的位置为q
                }
                else if (len[i-1][j] >= len[i][j-1]) {          //len数组从上方获取值的情况
                    len[i][j] = len[i-1][j];                    //上方数字更大，则直接拿过来数组中上方的数字
                    path[i][j] = 'u';                           //记录路径来自上方(up)
                }
                else {
                    len[i][j] = len[i][j-1];                    //len数组从左边获取值的情况
                    path[i][j] = 'l';                           //记录路径来自左边(left)
                }
            }
        }
        return path;
    }

    //递归获得最终的最长公共子序列字符串
    void getString(vector<vector<char>> b, string s1, int i, int j, string& s){
        if(i ==0 || j == 0) return;
        if(b[i][j] == 'q') {
            getString(b, s1, i-1, j-1, s);            //如果当前路径是左上方来的
            s.push_back(s1[i-1]);                     //则记录该字符到最终串中
        }
        else if(b[i][j] == 'u'){
            getString(b, s1, i-1, j, s);              //如果路径是上方来的则直接沿上方递归
        }
        else {
            getString(b, s1, i, j-1, s);              //如果路径是左边来的则直接沿着左边递归
        }
    }
    string LCS(string s1, string s2) {
        // write code here
        string s = "";
        vector<vector<char>> path = LCS_path(s1, s2);
        getString(path, s1, s1.size(), s2.size(), s);
        return s == "" ? "-1" : s;
    }
};

复杂度分析

• 时间复杂度：，主要是二维数组的遍历过程
• 空间复杂度：，由于二维数组的空间申请

方法二：动态规划优化（单二维数组，可通过）

通过一个记录长度的二维数组的方式进行问题处理，最终的思路是类似方法一的，但是利用的记录来自记录长度的数组，也是一种不错的方法，而且空间上优化了。

class Solution {
public:
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    vector<vector<int>> LCS_path(string s1, string s2) {
        // 和方法一完全一致的部分
        int m = s1.size();
        int n = s2.size();
        vector<vector<int>> len(m+1, vector<int>(n+1, 0));
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(s1[i-1] == s2[j-1]) {
                    len[i][j] = len[i-1][j-1] + 1;
                }
                else if (len[i-1][j] >= len[i][j-1]) {
                    len[i][j] = len[i-1][j];
                }
                else {
                    len[i][j] = len[i][j-1];
                }
            }
        }
        return len;
    }

    string getString(vector<vector<int>> len, string s1, string s2, int i, int j) {
        string s = "";
        while(len[i][j] >= 1) {
            if(s1[i-1] == s2[j-1]) {                    //从表格右下角开始，如果出现两字符串字符相等的部分，则知道该字符是一定在最后的最长公共子序列中的。
                s += s1[i-1];
                i--;
                j--;
            }
            else if(len[i-1][j] >= len[i][j-1]) i--;    //如果两个字符不匹配，则按照方向递减往回找
            else j--;
        }
        reverse(s.begin(),s.end());                     //我们找的路线是逆序的，最终序列要倒序回来
        return s;
    }
    string LCS(string s1, string s2) {
        // write code here
        string s = "";
        vector<vector<int>> len = LCS_path(s1, s2);
        s = getString(len, s1, s2, s1.size(), s2.size());
        return s == "" ? "-1" : s;
    }
};

复杂度分析

• 时间复杂度：，主要是二维数组的遍历过程
• 空间复杂度：，由于二维数组的空间申请