0897

897. 最长公共子序列

题目

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

输入格式

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

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

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

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

输出格式

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

数据范围

$1 \le N,M \le 1000$

输入样例：

4 5
acbd
abedc

输出样例：

3

题解

前置题目：0896

前置知识：无

本题知识：动态规划-线性DP

题目分析

本题的状态表示和集合划分还是比较难想，积累经验值~

想到状态表示之后，集合划分可能会比较想当然，但具体的表示含义仍需思考清楚。

根据集合的定义可以分为四种情况：

1. 第一个序列不包含第 i 个字母，第二个序列不包含第 j 个字母
2. 第一个序列不包含第 i 个字母，第二个序列包含第 j 个字母
3. 第一个序列包含第 i 个字母，第二个序列不包含第 j 个字母
4. 第一个序列包含第 i 个字母，第二个序列包含第 j 个字母

这四种情况的分别求解时思路要打开：

1. 简单，f[i-1, j-1]
2. f[i-1, j] 表示的是第二个序列的前 j 个字母中出现，但第 j 个字母出不出现不一定，但划分的情况中要求必须要包含第 j 个字母。尽管如此，仍可以使用 f[i-1, j] 用来求解的原因是这个值虽然可能比第二种情况的真实值要大，但却是小于等于所求值 f[i, j] 的。
3. f[i, j-1] 和 2 类似
4. 不一定存在，需要 a[i] == b[j]，这样就可以转化成 f[i-1, j-1] + 1

实现细节

• 本题的特别之处在于划分之后是做到不漏了，但没有做到不重，但只要求并集之后没有超过原有范围也无妨。

• 第一种情况实际上是被包含在第二种情况和第三种情况之中的，所以不需要重复求解

• 易证，满足第四种情况的解是会大于等于二三情况的最大值的

  f[i-1][j-1]+1 >= max(f[i-1][j], f[i][j-1])