题解 | 最长公共子序列

最长公共子序列
动态规划：

//链接：https://www.nowcoder.com/questionTerminal/4727c06b9ee9446cab2e859b4bb86bb8

#include <bits/stdc++.h>
using namespace std;

int getmaxlenght(const string &str1,const string &str2,vector<vector<int>> &dp){
    for(int i = 1; i <= str1.size(); i++){
        for(int j = 1; j <= str2.size(); j++){
            if(str1[i-1] == str2[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[str1.size()][str2.size()];
}
int main(){
    string str1,str2;
    getline(cin,str1);
    getline(cin,str2);
    vector<vector<int>> dp(str1.size()+ 1,vector<int>(str2.size()+ 1,0));
    int lenght = getmaxlenght(str1, str2, dp);

    if (lenght == 0) cout << -1;
    string ans;
    ans.resize(lenght);
    int index = lenght-1;
    int x = str1.size(), y = str2.size();
    while(index >= 0){
        if(y >= 1 && dp[x][y] == dp[x][y-1])
            y--;
        else if(x >= 1 && dp[x][y] == dp[x-1][y])
            x--;
        else{
            ans[index--] = str1[x-1];
            x--;
            y--;
        }
    }
    cout << ans;
    return 0;
}