文章目录

最长公共子序列题目描述题解 最长上升子序列题目描述题解解法一解法二 最长公共上升子序列题目描述题解

最长公共子序列

题目描述

给定两个长度分别为N和M的字符串A和B，求既是A的子序列又是B的子序列的字符串长度最长是多少。 输入格式 第一行包含两个整数N和M。 第二行包含一个长度为N的字符串，表示字符串A。 第三行包含一个长度为M的字符串，表示字符串B。 字符串均由小写字母构成。 输出格式 输出一个整数，表示最大长度。 数据范围 1≤N,M≤1000 输入样例： 4 5 acbd abedc 输出样例： 3

题解

状态计算考虑最后一个元素，分别考虑a[i], b[j] 是否在集合中，这里的集合是指既包含在a[1~i]中，又包含在b[1-j]中。0表示在，1表示不在。

#include <iostream> #include <cstring> #include <algorithm> #include <string> using namespace std; const int N = 1010; int f[N][N]; char a[N], b[N]; int main() { int n, m; cin >> n >> m; cin >> a + 1 >> b + 1; //避免下标越界，起始位置从1开始 for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { if(a[i] != b[j]) { f[i][j] = max(f[i - 1][j], f[i][j - 1]); } else { f[i][j] = f[i - 1][j - 1] + 1; } } } cout << f[n][m] << endl; return 0; }

最长上升子序列

题目描述

给定一个无序的整数数组，找到其中最长上升子序列的长度。 示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

题解

状态计算考虑最后一个元素，判断在a[1~i]中是否有一个元素a[k]( 0 =< k <= i)小于a[i] 小于的话就可以转移。

解法一

int lengthOfLIS(vector<int>& nums) { int n = nums.size(); vector<int> f(n + 1, 1); for(int i = 0; i < n; i++) { for(int j = 0; j < i; j++) { if(nums[j] < nums[i]) { f[i] = max(f[i], f[j] + 1); } } } int res = 0; for(int i = 0; i < n; i++) res = max(f[i], res); return res; }

解法二

依然是着眼于一个上升子序列的结尾的元素； 如果已经得到的上升子序列的结尾的数越小，遍历的时候后面接上一个数，就会有更大的可能性构成一个更长的上升子序列； 既然结尾越小越好，我们可以记录在长度固定的情况下，结尾最小的那个元素的数值，这样定义也是为了方便得到「状态转移方程」。 为了与之前的状态区分，这里将状态数组命名为 tail。 定义新状态（特别重要）：tail[i] 表示长度为 i + 1 的所有上升子序列的结尾的最小值。

int lengthOfLIS(vector<int>& nums) { int n = nums.size(); if(n < 2) return n; vector<int> tail; //长度为i的上升子序列末尾元素 tail.push_back(nums[0]); int end = 0; for(int i = 1; i < n; i++) { if(nums[i] > tail[end]) { tail.push_back(nums[i]); end++; } else { int l = 0, r = end; while(l < r) { int mid = l + r >> 1; if(tail[mid] < nums[i]) l = mid + 1; else r = mid; } tail[l] = nums[i]; } } return end + 1; }

最长公共上升子序列

题目描述

熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。 小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们研究最长公共上升子序列了。 小沐沐说，对于两个数列A和B，如果它们都包含一段位置不一定连续的数，且数值是严格递增的，那么称这一段数是两个数列的公共上升子序列，而所有的公共上升子序列中最长的就是最长公共上升子序列了。 奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子序列。 不过，只要告诉奶牛它的长度就可以了。 数列A和B的长度均不超过3000。 输入格式 第一行包含一个整数N，表示数列A，B的长度。 第二行包含N个整数，表示数列A。 第三行包含N个整数，表示数列B。 输出格式 输出一个整数，表示最长公共上升子序列的长度。 数据范围 1≤N≤3000,序列中的数字均不超过231−1 输入样例： 4 2 2 1 3 2 1 2 3 输出样例： 2

题解

1.状态表示： f[i][j]代表所有a[1 ~ i]和b[1 ~ j]中以b[j]结尾的公共上升子序列的集合； f[i][j]的值等于该集合的子序列中长度的最大值； 2.状态计算（对应集合划分）： 首先依据公共子序列中是否包含a[i]，将f[i][j]所代表的集合划分成两个不重不漏的子集： 不包含a[i]的子集，最大值是f[i - 1][j]； 包含a[i]的子集，将这个子集继续划分，依据是子序列的倒数第二个元素在b[]中是哪个数： 子序列只包含b[j]一个数，长度是1； 子序列的倒数第二个数是b[1]的集合，最大长度是f[i - 1][1] + 1； … 子序列的倒数第二个数是b[j - 1]的集合，最大长度是f[i - 1][j - 1] + 1；

算法优化： 优化第二层循环。因为a[i] == b[j], 第三层循环的作用是求小于b[j]的方案数，也即是求小于a[i]的方案数, 求完一个j后，剩下的j继续往后走变成j+1，但第一层循环i保持不变。即if(b[j + 1] = a[i]), 又会执行第三层循环，这时就会重复求解原来求过的数。

#include "iostream" using namespace std; const int N = 3010; int f[N][N]; int a[N], b[N]; int main(){ int n; cin>>n; for(int i = 1; i <= n; i++){ cin>>a[i]; } for(int i = 1; i <= n; i++){ cin>>b[i]; } //朴素算法 for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ f[i][j] = f[i-1][j]; if(a[i] == b[j]){ int mmax = 1; for(int k = 1; k < j; k++){ if(b[k]<b[j]){ mmax = max(mmax, f[i-1][k]+1); } } f[i][j] = max(f[i][j], mmax); } } } //优化后的算法 /* for(int i = 1; i <= n; i++){ int mmax = 1; for(int j = 1; j <= n; j++){ f[i][j] = f[i-1][j]; if(b[j]<a[i]) mmax = max(mmax, f[i-1][j]+1); if(a[i] == b[j]) f[i][j] = max(f[i][j], mmax); } } */ int res = 0; for(int i = 1; i <= n; i++) res = max(res, f[n][i]); printf("%d\n", res); return 0; }

链接：https://www.acwing.com/solution/content/4955/