题目描述

给定一个长度为 N 数组 a 和一个长度为 M 的数组 b。

请你求出它们的最长公共子序列长度为多少。

输入描述

输入第一行包含两个整数 N,M，分别表示数组 a 和 b 的长度。

第二行包含 N 个整数 a1,a2,...,an。

第三行包含 M 个整数 b1,b2,...,bn。

1≤N,M≤10^3，1≤ai,bi≤10^9。

输出描述

输出一行整数表示答案。

输入输出样例

示例 1

输入

1. 5 6 2. 1 2 3 4 5 3. 2 3 2 1 4 5

输出

4

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

这里有大佬讲解的思路具体讲解

思路

我们先介绍概念：

最长公共子序列（Longest Common Subsequence，LCS）：一个给定序列的子序列，是在该序列中删去若干元素后得到的序列。

给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。最长公共子序列是长度最长的子序列。

具体做法：

我们用dp[i][j]表示A序列的前i个值和B序列前j个值得最长公共子序列得个数，通过状态转移方程，最终得到的dp[n][m]就是我们所求得解

状态转移方程：

1. 当ai=bj 时，已求得 Ai−1 和Bj−1 的最长公共子序列，在其尾部加上 ai 或 bj 即可得到 Ai 和 Bj 的最长公共子序列。状态转移方程是：dp[i][j] = dp[i-1][j-1] + 1
2. 当 ai！=bj 时，求解两个子问题：Ai−1 和 Bj 的最长公共子序列；Ai 和 Bj−1 的最长公共子序列。取其中的最大值，状态转移方程是：dp[i][j] = max(dp[i-1][j] + dp[i][j-1])

依据状态转移方程，我们就可轻松得到最终的结果了。

注意，我们的dp表中第零行和零列的值都为零，意思是空和序列的公共子序列为零，因为这一点，所以我们也要给输入的字符串前面加0占位。

代码

1. n,m=map(int,input().split()) 2. a=[0] 3. b=[0] 4. a+=list(map(int,input().split())) 5. b+=list(map(int,input().split())) 6. num=1000 7. dp=[[0]*num for _ in range(num)] 8. for i in range(1,n+1): 9. for j in range(1,m+1): 10. if a[i]==b[j]: 11. dp[i][j]=dp[i-1][j-1]+1 12. else: 13. dp[i][j]=max(dp[i-1][j],dp[i][j-1]) 14. print(dp[n][m])