题目描述

给定两个长度分别为 N
和 M
的字符串 A
和 B
，求既是 A
的子序列又是 B
的子序列的字符串长度最长是多少。

输入格式
第一行包含两个整数 N
和 M
。

第二行包含一个长度为 N
的字符串，表示字符串 A
。

第三行包含一个长度为 M
的字符串，表示字符串 B
。

字符串均由小写字母构成。

输出格式
输出一个整数，表示最大长度。

数据范围
1≤N,M≤1000

样例

 4 5
acbd
abedc

输出

3

这道题我们怎么看呢，首先我们先用弄明白公共子序列是什么玩意
如图所示

A:a,c,b,d
B:a,b,e,d,c
    ||
  A:a,b,d
  B:a,b,d

从中我们可以发现什么？
发现解决这道题的绝妙方法————他们的结尾是一样的
而且不难发现，由此往前递推我们会发现一个奇妙的事件————每一位都是一样的
（好入机的言论）
但由此我们可以在正过来
依次枚举一下A,B的结尾元素
然后我们就得到了蓝书中的推导公式

    f[i][j]=max(f[i-1][j],f[i][j-1]);
            if(a[i]==b[j]){
            f[i][j]=max(f[i][j],f[i-1][j-1]+1);

然后从入机到LCS的教程就结束了；

C++ 代码

 #include<bits/stdc++.h>
using namespace std;
const int N=1e4;
char a[N],b[N];
int n,m;
int f[N][N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>b[i];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){  
        f[i][j]=max(f[i-1][j],f[i][j-1]);
            if(a[i]==b[j]){
            f[i][j]=max(f[i][j],f[i-1][j-1]+1);
            }
        }
    }
    cout<<f[n][m];
    return 0;
}