【打卡】牛客网：M65 最长公共子序列(二)

自己写的：

通过率（2/7）

被bp创到了，再也不自己写了。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    string LCS(string s1, string s2) {
        // write code here
        int n = s1.size();
        int m = s2.size();
        if(n==0 || m == 0)
            return "-1";
        vector<vector<string>> dp(n+1, vector<string> (m+1, ""));

        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++){
                if(dp[i-1][j] == "") //上面为空
                    dp[i][j] = dp[i][j-1]; //取左边

                else if(dp[i][j-1] == "")
                    dp[i][j] = dp[i-1][j]; //取上边

                else if(s1[i] == s2[j]){
                    dp[i][j] = dp[i-1][j] + s1[i];
                }

                else{
                    if(dp[i-1][j].length() == dp[i][j-1].length())
                        dp[i][j] = dp[i-1][j]; //取上边
                    else
                        dp[i][j] = dp[i][j-1]; //取左边
                }
            }

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                cout<<dp[i][j]<<" ";
            }
            cout<<endl;
        } 
        
        if(dp[n][m] == "")
            return "-1";

        return dp[n][m];
    }
};

模板的：

1. 动态规划时，用了dp和b两个矩阵：? ??
   1. 矩阵dp只记录最长公共子序列的长度，在动态规划的时候，再用一个矩阵b记录路径。
2. 最后，对矩阵b用【递归】，来将dp的int型变成string型。

class Solution {
public:
    string x = "";
    string y = "";
    string ans(int i, int j, vector<vector<int>> &b){
        if(i == 0 || j == 0)
            return "";
        if(b[i][j] == 1){
            return ans(i-1, j-1, b) + x[i-1];
        }
        else if(b[i][j] == 2)
            return ans(i-1, j, b);
        else
            return ans(i, j-1, b);
    }

    string LCS(string s1, string s2) {
        // write code here
        int n = s1.size();
        int m = s2.size();
        if(n==0 || m == 0)
            return "-1";
        vector<vector<int>> dp(n+1, vector<int> (m+1));
        vector<vector<int>> b(n+1, vector<int> (m+1));
        x = s1;
        y = s2;
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= m; j++){
                if(s1[i-1] == s2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    b[i][j] = 1;
                }
                else{
                    if(dp[i-1][j] > dp[i][j-1]){
                        dp[i][j] = dp[i-1][j];
                        b[i][j] = 2;
                    }
                    else{
                        dp[i][j] = dp[i][j-1];
                        b[i][j] = 3;
                    }
                }
            }

        string ANSstr = ans(n,m,b);
        cout<<ANSstr;
        return ANSstr == "" ? "-1" : ANSstr;

    }
};