题目描述

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

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

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

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

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

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

数据范围
1≤N≤1000,

样例

输入样例：
4 5
acbd
abedc
输出样例：
3

DP

求：两个字符串的公共子序列中最长的长度是多少

在两个字符串相同数位情况下，会有2^n个公共子序列

1.状态表示
f[i,j]表示A[1~i],B[1~j]的公共子序列的集合
属性为最长的公共子序列的长度

2.状态计算
找到最后一个不同点，A[i],B[j]是否包含在子序列中，所以一共可以划分为4个子集

• 当A[i],B[j]都包含在，则只有当A[i]=B[j]才会有这种情况，最大值为f[i-1,j-1]+1
• 当A[i]B[j]都不包含，最大值为f[i-1,j-1]
• 当不包含A[i],包含B[j]。不可以简单的认为最大值为f[i-1,j],因为这个集合表示从A[1~i-1],B[1~j]中选，可是B[j]不一定包括在内，并且没有很好的公式可以单独的计算这个子集。！！！但是，在求最大或最小值的时候，划分子集不一定要做到不重（不漏还是一定要的），因为在一个集合中即使划分的子集间有重复，并不影响最大值最小值的大小。而f[i-1,j]中当B[j]不包含在内时，恰好就是第二种情况。但是f[i-1,j]同时也包含了我们要求的方案（B[j]包含），所以这里有一定的重复，但是不会影响结果，那不妨就用f[i-1,j]来求解这个划分的子集。
• 当包含A[i],不包含B[j]时，同理，可以用f[i,j-1]来求解。

所以用f[i-1,j],f[i,j-1],f[i,j]+1可以覆盖整个f[i,j]

C++ 代码

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

const int N=1010;

int n,m;
char a[N],b[N];
int f[N][N];

int main(){
    cin>>n>>m;
    cin>>a+1>>b+1;
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i]==b[j])  f[i][j]=f[i-1][j-1]+1;
            else f[i][j]=max(f[i-1][j],f[i][j-1]);

        }
    }
    cout<<f[n][m];
    return 0;
}