给定两个数列\(A, B\)，如果他们都包含一段位置不一定连续的数，且数值是严格递增的，那么称这一段数是两个数列的公共上升子序列。求\(A\)和\(B\)的最长公共上升子序列。
输入格式
第一行包含一个整数\(N\)，表示\(A\)和\(B\)的长度。
第二行包含\(N\)个整数，表示数列\(A\)。
第三行包含\(N\)个整数，表示数列\(B\)。
输出格式
输出一个整数，表示最长公共上升子序列的长度。
数据范围
\(1 ≤ N≤ 3000\)，序列中的数字均不超过\(2^{31} - 1\).
输入样例
4 2 2 1 3 2 1 2 3输出样例
2 2. 朴素解法\(O(n^3)\)朴素解法将最长公共子序列和最长上升子序列模型相结合。
用\(f[i][j]\)表示第一个序列的前\(i\)个数，和第二个序列的前\(j\)个数，且最后一个数为\(b[j]\)的最长公共上升子序列的长度。
则可以根据\(a[i]\)是否等于\(b[j]\)进行分类讨论。
\[f[i][j]=\left\{ \begin{array}{rcl} f[i - 1][j] & & {a[i] != a[j]}\\ max_{k < j且b[k] < b[j]}(f[i][j], f[i- 1][k]) & & {a[i] == b[j] }\\ \end{array} \right. \]