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

//经典动态规划的题
#include<bits/stdc++.h>
using namespace std;
int main(){
    string str1,str2;
    cin>>str1>>str2;
    //申请一个二维数组dp
    int n=str1.size();
    int m=str2.size();
    //申请一个n行m列的二维表dp
    int dp[n][m];
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            dp[i][j]=0;
        }
    }
    dp[0][0]=str1[0]==str2[0]?1:0;
    //dp[i][j]的含义为：str1[0..i]和str2[0..j]的最长公共子序列长度是多少
    //所以最后的结果就是dp[n-1][m-1]的值
    //对于dp表的第一行初始化如下
    for(int i=1;i<m;i++){//第一行只要之前有一个1，后面的值就都为1
        dp[0][i]=str1[0]==str2[i]?1:(dp[0][i-1]>dp[0][i]?dp[0][i-1]:dp[0][i]);
    }
    //对于第一列同理
    //只要之前有一个位置的值是1下面的值就全都是1
    for(int i=1;i<n;i++){
        dp[i][0]=str2[0]==str1[i]?1:(dp[i-1][0]>dp[i][0]?dp[i-1][0]:dp[i][0]);
    }
    //对于不是第一行也不是第一列的其他位置如歌求解dp[i][j]的值
    //dp[i][j]的值就三种可能性
    //1.要么等于dp[i-1][j]2.要么等于dp[i][j-1]3.要么等于dp[i-1][j-1]+1,此时str1[i]=str2[j]
    //取这三种情况里最大的那一种
    for(int i=1;i<n;i++){
        for(int j=1;j<m;j++){
            if(str1[i]==str2[j]){
                dp[i][j]=dp[i-1][j-1]+1;
            }
            dp[i][j]=dp[i-1][j]>dp[i][j]?dp[i-1][j]:dp[i][j];
            dp[i][j]=dp[i][j-1]>dp[i][j]?dp[i][j-1]:dp[i][j];
        }
    }
    //此时最长公共子序列的长度就求出来了，就为dp[n-1][m-1];
    //怎么根据dp表求出最长公共子序列呢？
    //把这个过程逆序一下即可
    int row=n-1,cow=m-1;
    int len=dp[row][cow];
    char res[len];
    int index=len-1;
    while(index>=0){
        if(row>0&&dp[row][cow]==dp[row-1][cow])
        row--;
        else if(cow>0&&dp[row][cow]==dp[row][cow-1])
        cow--;
        else{
            res[index--]=str1[row];
            row--;
            cow--;
        }
    }
    if(dp[n-1][m-1]==0){
        cout<<-1<<endl;
        return 0;
    }
    for(int i=0;i<dp[n-1][m-1];i++)
        cout<<res[i];
    return 0;
}