ACM程序设计篇：如何实现动态规划求解最长公共子序列（LCS）？

本文共计1843个文字，预计阅读时间需要8分钟。

动态规划+P1439+【模板】最长公共子序列+-+谷歌 | 计算机科学教育新生态+(luogu.com.cn)+题目描述+给出+1,2,...,n+的+两个排列+P+1+和+P+2+，求它们的+最长公共子序列+。输入格式+第一行是+一个+数字+。

动态规划

P1439 最长公共子序列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

给出 1,2,…,n 的两个排列 P1 和 P2 ，求它们的最长公共子序列。

输入格式

第一行是一个数 n。

接下来两行，每行为 n 个数，为自然数 1,2,…,n 的一个排列。

输出格式

一个数，即最长公共子序列的长度。

输入输出样例

输入 #1

5 3 2 1 4 5 1 2 3 4 5

输出 #1

3

说明/提示

• 对于 50% 的数据， n≤1000；
• 对于 100% 的数据， n≤100000。