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

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

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

动态规划

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。