题目描述

提供了注释，主要是不懂如何输出多个最优方案。

(线性DP + DFS) 复杂度玄学

C++ 代码

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;

//LCS记录多种方案：
//

const int N=100;
int n,m;
char s1[N];
char s2[N];
int f[N][N];
char path[N];


//可以提前预处理来优化
void dfs(int i,int j,int u,int len)
{
    if(u>len)
    {
        puts(path+1);
        return ;
    }

    if(s1[i]==s2[j])
    {
        path[u]=s1[i];
        dfs(i+1,j+1,u+1,len);
    }
    else
    {
        for (int k = 0; k < 26; k ++ )  //枚举是可行的
        {
            int a = 0; // 在s1中，下一个字母k出现在哪里
            int b = 0; // 在s2中，下一个字母k出现在哪里

            for (int x = i; x <= n; x ++ )
                if (s1[x] == 'a' + k)
                {
                    a = x;
                    break;
                }

            for (int x = j; x <= m; x ++ )
                if (s2[x] == 'a' + k)
                {
                    b = x;
                    break;
                }

            if (a && b && f[a][b] == f[i][j])   //虽然可能有两个位置的f值是相同的
                                                //但是我们可以保证，如果是两个位置对分别相等（但并不是最优）的情况下，f的值一定不同，比如样例中的第二位。
            {
                dfs(a, b, u, len);
            }
        }
    }
}

int main()
{
    scanf("%s",s1+1);
    scanf("%s",s2+1);

    n=strlen(s1+1);   
    m=strlen(s2+1);

    for(int i=n;i>=1;i--)
    {
        for(int j=m;j>=1;j--)
        {
            f[i][j]=max(f[i+1][j],f[i][j+1]);

            if(s1[i]==s2[j])
            {
                f[i][j]=max(f[i][j],f[i+1][j+1]+1);
            }
        }
    }

    dfs(1,1,1,f[1][1]);

    //cout<<f[1][1]<<endl;

    return 0;
}