897 最长公共子序列（模板题）

梦里梦外; 2022-08-31 12:26 139阅读 0赞

**1. 问题描述：**

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

**输入格式**

第一行包含两个整数 N 和 M。  
第二行包含一个长度为 N 的字符串，表示字符串 A。  
第三行包含一个长度为 M 的字符串，表示字符串 B。  
字符串均由小写字母构成。

**输出格式**

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

**数据范围**

1 ≤ N，M ≤ 1000

**输入样例：**

4 5  
acbd  
abedc

**输出样例：**

3  
来源：[https://www.acwing.com/problem/content/899/][https_www.acwing.com_problem_content_899]

**2. 思路分析：**

这是一道经典的dp问题，我们可以理解其中的过程然后记住代码即可。动态规划主要有两个分析的步骤：① 状态表示 ② 状态计算。 因为涉及到两个字符串所以我们需要定义一个二维数组（一般字符串的动态规划都是这样定义的，一个字符串定义一维数组，两个字符串定义二维数组），可以定义dp\[i\]\[j\]为A\[1~i\]与B\[1~j\]最长公共子序列的长度，如何进行状态的计算呢？状态计算对应集合的划分，也即dp\[i\]\[j\]划分为若干个子集，每个子集中求解最大值就可以得到整个集合的最大值，划分的集合就可以表示状态计算。我们在划分集合的时候一般是寻找最后一个不同点，这里我们可以以字符串A与字符串B的最后一个字符是否包含在子序列中间划分集合，可以发现我们可以将其分为四大类：

*  i，j对应的字符都包含
 *  i对应的字符包含，j对应的字符不包含
 *  i对应的字符不包含，j对应的字符包含
 *  i，j对应的字符军不包含

对于第一类和第四类其实比较好分析，主要是第二类和第三类的集合的分析，对于第二类表示的含义并不完全等价dp\[i\]\[j - 1\]，因为dp\[i\]\[j - 1\]表示的是A\[1~i\]和B\[1~j-1\]最长公共子序列的长度，可能包含i对应的字符，也可能不包含i对应的字符，所以dp\[i\]\[j - 1\]是包含了第二类的情况但是两者并不是完全等价的，但是由于计算的是最大值，所以我们在计算第二类的时候使用dp\[i\]\[j - 1\]来代替第二类的情况，这样是可以完全计算出第二类的情况对于答案是没有什么影响的，对于第三类也是类似的，对于第四类可以发现其实计算的所有方案是包含在第三类dp\[i-1\]\[j\]中的，因为我们在计算的时候对于第三类也是需要分为四种情况这样考虑的时候就包含了当前第四类的情况，所以我们实际在计算的时候是不用考虑第四类的，主要是其中的分析过程，我们理解之后可以将代码记住即可。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70][]

**3. 代码如下：**

if __name__ == '__main__':
        # 最长公共子序列模板
        n, m = map(int, input().split())
        a = input()
        b = input()
        dp = [[0] * (m + 1) for i in range(n + 1)]
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                # 计算第二类与第三类的情况
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
                # 当第一类存在的时候才计算
                if a[i - 1] == b[j - 1]:
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1)
        print(dp[n][m])

[https_www.acwing.com_problem_content_899]: https://www.acwing.com/problem/content/899/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70]: /images/20220829/70792c9909d94e55b8e7e5375d523c1e.png