2629. 最长公共子序列

【题目描述】

给定长度为$m$的序列$a=\{a_1,a_2,\cdots,a_m\}$和长度为$n$的序列$b=\{b_1, b_2, \cdots, b_n\}$，若有一个序列$c=\{c_1, c_2,\cdots,c_k\}$既是$a$的子序列也是$b$的子序列，则称序列$c$为$a$和$b$的公共子序列。

例如：对于两个序列$a=\{1,2,3,2,4,1,2\}$和$b=\{2,4,3,1,2,1\}$，序列$\{2,3,1\}$是$a$和$b$的一个公共子序列，序列$\{2,3,2,1\}$也是$a$和$b$的一个公共子序列。

在这些公共子序列中，找到最长的一个，这就是最长公共子序列问题(Longest Common Subsequence, LCS)。

【输入格式】

第一行两个整数$m,n(m,n\leq 3000)$，分别表示两个序列的长度。

第二行$m$个整数，表示第一个序列的元素。

第三行$n$个整数，表示第二个序列的元素。

【输出格式】

一行一个整数，表示最长公共子序列长度。

【样例输入】

7 6
1 2 3 2 4 1 2
2 4 3 1 2 1

【样例输出】

4

【样例说明】

子序列2 3 2 1、2 4 1 2、2 4 2 1等都是最长公共子序列。