输出路径专题

//递归输出LCS
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 2e3+9;
char s[N],t[N];
int dp[N][N];
int path[N][N];
void print(int i,int j)
{
    if(i == 0 || j == 0) return;
    if(path[i][j] == 1)
    {
        print(i-1,j-1);
        printf("%c",s[i]);
    }
    else if(path[i][j] == 2)
    {
        print(i-1,j);
    }
    else if(path[i][j] == 3)
    {
        print(i,j-1);
    }
}
int main()
{
    scanf("%s%s",s+1,t+1);
    int n = strlen(s+1),m = strlen(t+1);
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            if(s[i] == t[j])
            {
                dp[i][j] = dp[i-1][j-1] + 1;
                path[i][j] = 1;
            }
            else if(dp[i-1][j] >= dp[i][j-1])
            {
                dp[i][j] = dp[i-1][j];
                path[i][j] = 2;
            }
            else
            {
                dp[i][j] = dp[i][j-1];
                path[i][j] = 3;
            }
        }
    }
    print(n,m);
    return 0;
}