LCS题解

· · 题解

原题传送门

Part0：

首先，我们需要搞明白 LCS 是什么东西。

顾名思义，LCS 即最长公共子序列的缩写。举个简单的例子，字符串 abcd 与 accd，它们的最长公共子序列为 acd。

现在切入正题。

Part1：

这道题可以分成两个部分，我们可以先求出 LCS 的长度。

LCS 的长度求法为暴力 DP，我们可以设置状态 dp[i][j] 为 s 的前 i 项与 t 的前 j 项的 LCS。接下来分类讨论：

由此，我们可以写下代码：

for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
        if(s[i]==t[j]) dp[i][j]=dp[i-1][j-1]+1;//如果两个字符相等，答案为前一项的 LCS+1
        else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);//不相等，在前两个中求最大

输入：

abracadabra
avadakedavra

输出：

7

至此，LCS 求长度的代码就完成了。

时间复杂度 O(n \times m) 。

Part2：

题目中让我们求的是 LCS 的字符串，且只要是满足是 LCS 的任意字符串即可。那我们在做动态规划时，就要把动态转移的最优路径路径保存下来。

我们可以用布尔 x[i][j] 来表示从上一个状态至此 i 是否增加， y[i][j] 来表示从上一个状态至此 j 是否增加（可以理解为二维坐标）。

由于上面的代码中，我们已经通过判断、求最大，找出了 LCS 长度的最优解，因此只需稍稍修改，即可变为 AC Code：

#include<bits/stdc++.h>
using namespace std;
int n,m,i,j,dp[3010][3010];char a[3010],b[3010];bool x[3010][3010],y[3010][3010];
void print(int i,int j){
    if(i==0||j==0) return ;
    print(i-x[i][j],j-y[i][j]);//继续往前找
    if(a[i]==b[j]) cout<<a[i];//如果相等，说明这个字符属于LCS
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>a+1>>b+1;
    n=strlen(a+1);m=strlen(b+1);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1,x[i][j]=1,y[i][j]=1;
            else if(dp[i-1][j]>dp[i][j-1]) dp[i][j]=dp[i-1][j],x[i][j]=1;
            else dp[i][j]=dp[i][j-1],y[i][j]=1;//LCS
    print(n,m);//以栈的形式输出（逆向输出）
    return 0;
}

注：为方便理解，原题中的 s、t 数组在本代码中以 a、b 代替 （其实就是懒得改了）。