最长公共子序列

上一篇动态规划总结

个人思路

对比备忘录方法（递归）和动态规划（递推）

备忘录方法

• 备忘录方法要用递归实现
• 递归是自顶向下的解决问题的：即从目标开始，将问题划分，对子问题求解，直到边界
• 递归前对备忘录进行查询，当前备忘录未被填写时，则进行递归，否则直接返回备忘录的内容（核心，提高算法效率）
• 当整个问题的求解过程中有大量子问题无需求解时，备忘录更省时
• 一般要对备忘录进行初始化，为了之后快速判断是否有已经填写过备忘录

动态规划递推式

• 通过循环实现
• 递推式是自下而上解决问题的：即从边界开始，逐步对问题求解，直到抵达目标
• 当整个问题的求解过程中全部都要进行计算时，则应该使用递推式

思路

dp[i][j]表示字符串1长度为i与字符串2长度为j的最长公共子序列

自顶向下分析：

• 求最优解：求的是两个字符串的最长公共子序列
• 最优子结构：整个字符串的最长公共子序列依赖于其中子串的最长公共子序列，即去掉最后一个或若干个字符，剩下的字符串所记录的值仍然是最长公共子序列
• 重叠子问题：计算过程中会多次比较两个字符串的子串

自下而上解决问题：

• 边界：两个字符串出现空串时，最长公共子序列为0，即dp[i][0]和dp[0][i]均为0，i的取值范围是0~两个字符串各自的长度
• 状态转移：
  • 当两个字符串当前位置字符相等时，str[i ]==str[j]，最长公共子序列要在两个字符串各自的上一位基础上+1，即dp[i][j] = dp[i - 1][j - 1] + 1
  • 当两个字符串当前位置字符不相等时，str[i]!=str[i]，最长公共子序列无法继续延长，则继承dp[i][j - 1]，dp[i - 1][j]的最大值，即dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
• 时间复杂度：O(m * n)，m，n为字符串的长度

注意

• i,j表示的是长度，访问元素的时候需-1
• 回溯法输出所有解：
  • 从dp备忘录的最后一位开始回溯
  • 若当前位置数值与其左侧位置数值相同时，说明从左侧转移到当前位置的LCS没有延长
  • 若当前位置数值与其上侧位置数值相同时，说明从上侧转移到当前位置的LCS没有延长
  • 若当前位置数值与其上侧、左侧均不相同，说明此时LCS得到延长，应记录当前位置所对应的字符
• 最后要注意回溯法是逆序遍历，因此输出时要逆序输出

个人思路代码

备忘录方法+回溯输出所有解

/*
 * @Author: LLX 
 * @Date: 2020-10-31 19:19:33 
 * @Last Modified by: SEUer
 * @Last Modified time: 2020-10-31 19:20:11
 */
#include<bits/stdc++.h>
using namespace std;
//dp[i][j]表示字符串1长度为i与字符串2长度为j的最长公共子序列
//i,j表示的是长度，访问元素的时候需-1
string str1, str2;
int len1, len2;
string ans;//存放具体的最大公共子序列
int lcs;//存放最大公共子序列的长度
void findLCS(vector<vector<int> >& dp, int x, int y){
    if(x <= 0 || y <= 0){
        if(ans.size() == lcs){
            reverse(ans.begin(), ans.end());
            cout << "lcs：" << ans << endl;
        }
        ans = "";
        return;
    }
    if(dp[x - 1][y] == dp[x][y]){//上方数值与当前位置数值相同，说明LCS长度没有改变
        findLCS(dp, x-1, y);
    }
    if(dp[x][y - 1] == dp[x][y]){//左侧数值与当前位置数值相同，说明LCS长度没有改变
        findLCS(dp, x, y- 1);
    }
    if((dp[x - 1][y] != dp[x][y]) && (dp[x][y - 1] != dp[x][y])){//左、上均不相同，说明LCS长度增加了，则向左上方移动（即字符串1，字符串2均前移一位）
        ans += str1[x -1];
        findLCS(dp, x- 1, y - 1);
    }
}
int DP(vector<vector<int> >& dp, int i, int j){
    if(dp[i][j] != -1){
        return dp[i][j];
    }
    if(str1[i - 1] == str2[j - 1]){
        dp[i][j] = DP(dp, i - 1, j -1) + 1;
    }else{
        dp[i][j] = max(DP(dp, i, j - 1), DP(dp, i - 1, j));
    }
}
int main(){
    cin >> str1 >> str2;
    len1 = str1.size();
    len2 = str2.size();
    vector<vector<int> > dp(len1 + 5, vector<int> (len2 + 5, -1));
    //边界
    for(int i = 0; i < dp.size(); ++i){
        dp[i][0] = 0;
    }
    for(int i = 0; i < dp[0].size(); ++i){
        dp[0][i] = 0;
    }
    lcs = DP(dp, len1, len2);
    cout << "length of lcs：" << lcs << endl;
/*
bdcaba
abcbdab
*/
//输出dp备忘录
    cout << "matrix of dp:" << endl;
    for(int i = 0; i <= len1; ++i){
        for(int j = 0; j <= len2; ++j){
            if(dp[i][j] >= 0)
                cout << "+" << dp[i][j] << " ";
            else
                cout << dp[i][j] << " ";
        }
        cout << endl;
    }
    findLCS(dp, len1, len2);
    //cout << ans << endl;
    system("pause");
    return 0;
}

递推式方法——Leetcode

class Solution {
public:
    int dp[1005][1005];
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size();
        int n = text2.size();
        //递推
        for(int i = 1; i <= m; ++i){
            for(int j = 1; j <= n; ++j){
                if(text1[i - 1] == text2[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else{
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
};