模板 | 最长公共子序列模板及问题详解

使用例题：最长公共子序列（原题链接）

题意：

给你两个字符串text1，text2，求两串字符串中的共有最长字序列。

代码详解：

int longestCommonSubsequence(string text1, string text2) {
    const int N=1e3+10;
    //初始化为0
    int dp[N][N]={0};
    int n=text1.size();
    int m=text2.size();
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
        	//i-1因为字符串从0开始记数
            //倘若字符相同，则字符共有个数加一
            if (text1[i-1]==text2[j-1])dp[i][j]=dp[i-1][j-1]+1;
            //否则考虑不取text1末的字符的情况，或不取text2字符末的情况
            else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    return dp[n][m];
}

问题一：

为什么max里只存在两种情况？

原因：当两个字符出现不同时，说明此时两个字符串中的字符需要考虑取其中一个选取，此时存在两种情况，1.不取text1字符串的末尾，2.不取text2字符串的末尾，即dp[i-1][j]和dp[i][j-1]两种情况。假设比较dp[i-1][j-1]代表同时舍弃两个字符，此时相当于没做出改变。

问题二：

编写代码输出最长公共子序列的长度和其中一个最长公共子序列。

本代码采用递推的形式，因为查找的代码从左上至右下，所以可以使用从右下至左上的形式输出，因此代码的移动方式分为三种，即当字符不相同时，比较上边和左边的值，当字符相同时，移至左上，并输出字符。

alt

void print(int i, int j){
	//当a或者b的长度完全跑完时，停止代码
    if(i == 0 || j == 0)return;
    //优先考虑格子内字符不同的情况，避免因为过早满足判断字符相同情况而暴毙
    if(dp[i][j]==dp[i-1][j])print(i-1,j);//考虑上边格子符合条件
    else if (dp[i][j]==dp[i][j-1])print(i,j-1);//考虑左边代码是否符合
    else if(dp[i][j]==dp[i-1][j-1]+1)
    {
    	//符合则移至左上
        print(i-1,j-1);
        cout<<a[i-1];
    }
}

问题三：

请使用滚动数组压缩空间、计算最长公共子序列方案数。（核对链接）

首先先解决如何计算最长公共子序列的方案数，依据递推的思维，从代码的移动方式可知，存在三种移动方式，因此可以推出当前的方案数由上一步的方案数推移得到。但此时，存在一种特殊情况，即dp[i-1][j]和dp[i][j-1]都来自dp[i-1][j-1]时，代码存在重复操作，因此需要进行特殊判断，当满足该条件时，减去dp[i-1][j-1]。

#include<bits/stdc++.h>
using namespace std;

const int N=1e6+10,M=1e8;
//使用滚定数组压缩空间
int dp[2][N]={0},ans[2][N];
string a,b;


int main(){
    cin >>a>>b;
    int n=a.size();
    int m=b.size();
    //题意中，字符串末存在'.'
    n--;
    m--;
    //初始化方案数
    for (int i=0;i<=m;i++)ans[0][i]=1;
    ans[1][0]=1;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
        	//初始化方案数，避免不能使用的情况
            ans[i & 1][j]=0;
            if (a[i-1]==b[j-1])
            {
                dp[i & 1][j]=dp[i-1 & 1][j-1]+1;
                //当字符相同，方案来源于左上
                ans[i & 1][j]+=ans[i-1 & 1][j-1];
            }
            else dp[i & 1][j]=max(dp[i-1 & 1][j],dp[i & 1][j-1]);
            //字符不相同，判断左边和上边两个的方案来源
            if (dp[i & 1][j]==dp[i & 1][j-1])ans[i & 1][j]+=ans[i & 1][j-1];
            if (dp[i & 1][j]==dp[i-1 & 1][j])ans[i & 1][j]+=ans[i-1 & 1][j];
            //特判来源特殊情况
            if (a[i-1] != b[j-1] && dp[i & 1][j]==dp[i-1 & 1][j-1])ans[i & 1][j]-=ans[i-1 & 1][j-1];
            ans[i & 1][j]=ans[i & 1][j]%M;
        }
    }
    //判断滚动数组，最后存入的结果是在1，还是0
    if (n & 1)cout <<dp[1][m]<<"\n"<<ans[1][m]<<"\n";
    else cout <<dp[0][m]<<"\n"<<ans[0][m]<<"\n";
    return 0;
}