最長共通部分列 (Longest Common Subsequence)
2つの数列
a と b が与えられ、それぞれの長さは n と m です。この2つの数列における最長共通部分列の長さを求めてください。💡
「部分列」とは、元の数列からいくつか（あるいはまったく削除しなくてもよい）要素を取り除き、残った要素の順序を変えないままで得られる新しい数列のことを指します。
Input
最初の行には、空白で区切られた2つの整数
n と m (1 ≤ n, m ≤ 1000) が与えられます。
2行目には、数列 a を構成する要素 が空白区切りで与えられます (1 ≤ ≤ )。
3行目には、数列 b を構成する要素 が空白区切りで与えられます (1 ≤ ≤ )。Output
a と b の最長共通部分列の長さを表す整数を1つ出力してください。Examples
入力 | 出力 |
5 4
2 1 5 3 4
2 5 1 4 | 3 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB