最长公共子序列

题目描述

给定长度分别为 $n$、$m$ 的两个整数序列 $a$、$b$，求它们的最长公共子序列的长度。

一个序列的子序列是从原序列中删除若干个元素（可以不删除），保留其余元素的相对顺序得到的序列。子序列中的元素不要求连续。

如果一个序列同时是 $a$ 和 $b$ 的子序列，就称它为这两个序列的公共子序列。若两个序列没有相同元素，最长公共子序列的长度为 $0$。

输入格式

第一行包含两个整数 $n,m$，表示两个序列的长度。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

第三行包含 $m$ 个整数 $b_1,b_2,\ldots,b_m$。

输出格式

输出一个整数，表示两个序列的最长公共子序列长度。

样例 1

3 5
1 2 3
1 9 2 9 3

3

样例解释

序列 1 2 3 是两个序列的公共子序列，长度为 $3$。它在第二个序列中不连续，但出现顺序符合要求。

样例 2

4 5
1 2 4 5
4 1 3 3 2

2

样例解释

一种最长公共子序列为 1 2，长度为 $2$。

数据范围与评分

对于所有测试数据，$1\le n,m\le2000$，$-10^9\le a_i,b_j\le10^9$。

测试组	分值	附加限制
1	20 分	$n,m\le20$
2	30 分	$n,m\le200$
3	50 分	无

每组内全部测试点通过才能获得该组分数。