动态规划精讲(一)LC最长公共子序列
阅读原文时间:2023年07月08日阅读:3

P1439 【模板】最长公共子序列

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

第一行是一个数 n。

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

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

输入 #1

5
3 2 1 4 5
1 2 3 4 5

输出 #1

3

思路:

代码:

class Solution {
public:
int lengthOfLIS(vector& nums) {
int n=(int)nums.size();
if (n == 0) return 0;
vector dp(n, 0);
for (int i = 0; i < n; ++i) {
dp[i] = 1;
for (int j = 0; j < i; ++j) {
if (nums[j] < nums[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
return *max_element(dp.begin(), dp.end());
}
};