LCS

LCS（最长公共子序列）

1. 问题简介
2. 暴力算法
3. 打表算法
4. 特殊转LIS

问题概述：分别有两个长度为n,m的序列，求他们最长的公共子序列，如abcde(n=5)和jbddez(m=6)他们最长的公共子序列是bde。

思路：本来刚看到这一道题的时候，在想后推的过程后来想到可以把第一个作为主串第二个作为子串做一个贡献算法，比如32145和12345，前三个都为1到第四个的时候，先取一个最长的贡献，max=1，然后找到第四个就++，算了一下时间复杂度是o(mn)。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int n,m,s1[maxn],s2[maxn];
int dp1[maxn],dp2[maxn];
int main()
{
    memset(dp1,0,sizeof(dp1));
    memset(dp2,0,sizeof(dp2));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)    scanf("%d",&s1[i]);
    for(int i=1;i<=m;i++)    scanf("%d",&s2[i]);
    for(int i=1;i<=n;i++)
    {    int temp=0;
        for(int j=1;j<=m;j++)
        {
            if(s1[i]==s2[j])    dp1[i]=dp2[j]=temp+1;
            else    temp=max(dp2[j],temp);
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)    ans=max(ans,dp1[i]);
    printf("%d",ans);
    return 0;
}

然后是打表的思路，在之前的代码上改动了一下，有点类似背包的打表，还是把str2作为子串去做，做一个dp[i][j]代表str1遍历到i位，str2遍历到j位的时候，他们最长的公共子序列，当j++时候，如果不相等则选用继承的思想：dp[i][j]=max(dp[i][j-1],dp[i-1][j])，如果相等的情况(str1[i]=str2[j])就是迭代加一,dp[i][j]=dp[i-1][j-1]+1。

1 #include<iostream>
 2 using namespace std;
 3 int dp[1001][1001],a1[2001],a2[2001],n,m;
 4 int main()
 5 {
 6    cin>>n>>m;
 7    for(int i=1;i<=n;i++)scanf("%d",&a1[i]);
 8    for(int i=1;i<=m;i++)scanf("%d",&a2[i]);
 9    for(int i=1;i<=n;i++)
10     for(int j=1;j<=m;j++)
11      {
12          dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
13          if(a1[i]==a2[j])
14              dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
15      }
16    cout<<dp[n][m];
17    return 0;
18 }

然后看到一道特殊的情况利用离散化转LIS的方法（luogu）。

这道题目可以看到是两个全排列的情况，如果str1是一个递增的序列如12345，str2是另一个全排列如32145，那么求他们的LCS就是求str2的最长上升子序列了，因为str2的最长子序列一定是str1的子序列，这样就可以巧妙的利用LIS求解。但是如果说len(str1)!=len(str2)的情况，离散化的str1无法保证str2的子序列满足str1。

1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 1e5+10;
 4 map<int,int> m;
 5 int n,temp,a[maxn];
 6 int dp[maxn],p=0;
 7 int main()
 8 {
 9     scanf("%d",&n);
10     for(int i=1;i<=n;i++)    {scanf("%d",&temp);    m[temp]=i;}
11     for(int i=1;i<=n;i++)    {scanf("%d",&temp); a[i]=m[temp];}
12     for(int i=1;i<=n;i++)
13     {
14         if(a[i]>dp[p])    dp[++p]=a[i];
15         else{
16             int point=lower_bound(dp+1,dp+p,a[i])-dp;
17             dp[point]=a[i];
18         }
19     }
20     printf("%d",p);
21     return 0;
22 }

原文链接: https://www.cnblogs.com/GIN-DYD/p/15767230.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍