题目描述

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

输入格式

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

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

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

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

输出格式

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

数据范围

1≤N,M≤1000

输入样例：

4 5
acbd
abedc

输出样例：

3

主要考点

动态规划

类似题

密码脱落
最长公共子序列升级版

解题思路：

闫氏DP分析法

一、状态表示：f[i][j]
1. 集合：在第一个序列前i个字母中出现,且在第二个序列的前j个字母中出现的所有公共序列的长度的集合
2. 属性：最大值

二、状态计算：
1. 思想-----集合的划分
2. 集合划分依据：根据是否包含第一个序列的第i个字母,以及是否包含第二个序列的第j个字母,划分为4种情况.
3. 四种情况：00 01 10 11(不含a[i]不含b[j]、···)
00 f[i - 1][j - 1]
01 f[i - 1][j]//尽管不一致但所求是f[i - 1][j]的子集,最大值可以代替
10 f[i][j - 1]//尽管不一致但所求是f[i][j - 1]的子集,最大值可以代替
11 f[i - 1][j - 1] + 1
注意 1: f[i - 1][j]其实是分为两类的,含b[j]和不含b[j]两种情况
注意 2：所求集合间的最大值可以有重复,但不影响结果,因为f[i - 1][j]和f[i][j - 1]均是f[i][j]子集,二者
的最大值必然小于等于f[i][j]的最大值.

经验小结:
        在求数量的时候,集合的划分必须不重不漏.
        在求最大值的时候,集合的划分可以重复,但不影响结果.
        例如：求A,B,C最大值,可以先求A,B最大值,再求A,C最大值,B被算了两次,但不影响结果的正确性.

C ++代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;
const int N = 1010;

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

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> a[i];//读取字符串a
    for(int j = 1; j <= m; j ++) cin >> b[j];//读取字符串b

    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] << endl;

    return 0;
}