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

输入格式

第一行包含两个整数 N 和 M。

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

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

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

输出格式

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

数据范围

1≤N,M≤1000

输入样例：

4 5
acbd
abedc

输出样例：

3

y氏dp：

状态表示：f [ i , j ] 

集合： 所有在第一个序列的前 i 个字母中出现，且在第二个序列的前 j 个字母中出现的子序列 

属性：max

状态计算：以s1[ i ] , s2 [ j ] 是否包含在子序列中作为划分依据

 00表示s1 [ i ] 和 s2 [ j ]不出现在子序列f [ i ] [ j ]中

01表示s1 [ i ]不出现在子序列 ，s2 [ j ] 一定出现在子序列 。 10 11 以此类推

其中01 和 10 两种情况并不表示为 f [ i - 1 ][ j ]  和 f [ i ] [ j -1 ]。

f [ i - 1 ][ j ]表示的子序列为所有在第一个序列的前 i-1 个字母中出现，且在第二个序列的前 j 个字母中出现的最大值，并不说明s2[ j ]是一定出现在子序列中的。而01表示的是s1[ i ]不出现在子序列中，s2 [ j ]一定出现在子序列中 。但是，01 情况是包含在f [ i - 1 ][ j ]中的，所以可以用f [ i - 1 ][ j ]来表示 01 情况。 10 情况同理

由于01 和10 是包含的情况多余实际的，所以四种情况加起来会有重复情况，但是我们求的是最大值，所以重复情况并不影响结果。

00 情况是包含在了01 和10 情况里面的，所以代码中不需要体现。

#include
#includeusing namespace std;
const int N = 1e3+10;
int n , m ;
int f[N][N] ; //f[i][j] 所有在s1的前i个字母中和在s2的前j个字母中出现的子序列集合
char s1[N] , s2[N] ;int main()
{cin >> n >> m ;scanf("%s%s", s1+1 , s2+1);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(s1[i] == s2[j]) f[i][j] = max( f[i][j] , f[i-1][j-1] + 1) ;}}cout << f[n][m] ;return 0;
}