题目描述
给定一个长度为 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]就是我们所求得解
状态转移方程：
- 当ai=bj 时，已求得 Ai−1 和Bj−1 的最长公共子序列，在其尾部加上 ai 或 bj 即可得到 Ai 和 Bj 的最长公共子序列。状态转移方程是：dp[i][j] = dp[i-1][j-1] + 1
- 当 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])
