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

最长公共子序列：DP

思路：s1[i]与s2[j]是否匹配，dp[i+1][j+1]:以s[i]与s[j]为末尾匹配的最长公共序列长度， 由于要输出序列，所以得到公共子序列长度后，需要从后往前拼接

• ①是：dp[i+1][j+1]=dp[i][j]+1;都往前一个字符，再匹配
• ②否：dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]) s1往前一个字符，再匹配 或者 s2往前一个字符，再匹配

#include<iostream>
#include<string>
using namespace std;

const int maxn=5001;

string s1,s2;
int dp[maxn][maxn];

string longest(int m1,int m2){
    string ans;
    for(int i=0;i<=m1;i++)dp[i][0]=0;//初始化（边界为0）
    for(int i=0;i<=m2;i++)dp[0][i]=0;
    
    for(int i=0;i<m1;i++){
        for(int j=0;j<m2;j++){
            if(s1[i]==s2[j])dp[i+1][j+1]=dp[i][j]+1;
            else{
                dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
            }
        }
    }
    
    if(dp[m1][m2]==0){//公共子序列的长度为空
        ans="-1";
        return ans;
    }
    
    int posi=m1-1,posj=m2-1;
    while(posi>=0&&posj>=0){//逆向拼接
        if(s1[posi]==s2[posj]){//末位匹配
            ans=s1[posi]+ans;
            posi--;
            posj--;
        }
        else if(dp[posi][posj+1]>dp[posi+1][posj]){
            posi--;
        }
        else posj--;
    }
    return ans;
}

int main(){
    while(cin>>s1>>s2){
        int m1=s1.size();
        int m2=s2.size();
        cout<<longest(m1,m2)<<endl;
    }
    return 0;
}