建设网站聊天室,大连网站制作方法,我想开网店,制作网页模板这里#xff0c;为了更方便地解释#xff0c;我以洛谷上的一道典型题目为例#xff0c;为大家讲解处理最长公共子序列问题的几种常见方法。这道题目中规定了两个子序列的长度相等#xff0c;如果遇到不等的情况#xff0c;也只需要对长度稍作修改即可#xff0c;算法思想…这里为了更方便地解释我以洛谷上的一道典型题目为例为大家讲解处理最长公共子序列问题的几种常见方法。这道题目中规定了两个子序列的长度相等如果遇到不等的情况也只需要对长度稍作修改即可算法思想不变。 题目描述
给出 12…… n 的两个排列 A 和 B 求它们的最长公共子序列。
输入格式
第一行是一个数 n。
接下来两行每行为 n 个数为自然数 12…… n 的一个排列。
输出格式
一个数即最长公共子序列的长度。
样例输入 5 3 2 1 4 5 1 2 3 4 5
样例输出 3
提示
- 对于 50% 的数据 n 10^3 - 对于 100% 的数据 n 10^5。 方法1常规动态规划
要解决这道题目必然要使用动态规划。既然要用到动态规划就要知道状态转移方程。我们令L[i][j] 表示序列 A 和序列 B 的最长公共子序列的长度则状态转移方程如下
若a[i]b[j] 则 L[i][j]L[i-1][j-1] 1
若a[i]b[j] 则 L[i][j]max (L[i][j-1]L[i-1][j]
以表格的形式表示整个过程如下这里以 3 2 1 4 5 和1 2 3 4 5为例
i\j032145000000010001112001111301111140111225011123 填表的过程就相当于解题的过程第0行、第0列初始值都为0我们以第0行为参照先从左到右填满第1行再以第1行为参照从左到右填满第2行以此类推当表格填完后答案就出来了即为L[n][n]。 代码如下
# include iostreamusing namespace std;const int maxn 1e3 10;
int n;
int A[maxn];
int B[maxn];
int L[maxn][maxn];int main()
{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) {//对应状态转移方程if (A[i] B[j]) {L[i][j] L[i - 1][j - 1] 1;}else {L[i][j] max(L[i - 1][j], L[i][j - 1]);}}}cout L[n][n] endl;return 0;
} 这种方法是最基本的方法。容易看出它的时间复杂度是O(n^2)但这种方法有一个缺点就是对空间的要求非常高因为我们创建了一个二维数组 L所以空间复杂度为O(n^2) 如果 n 的值比较大那么我们就无法创建 L数组了。因此下面又给出了一种节省空间的办法。 方法2改进常规动态规划
我们的算法思想还和原来基本一致只不过我们要把二维数组 L 变成一个一维数组。实现的思想如下在填表的过程中我们可以发现当我们在填某一行时我们其实只需要用到上一行的数组作为参照表格中其他的部分并没有用。所以我们想到可以只创建一个一维数组 L 保存需要用作参照的上一行数据用一个变量 ans 保存计算得到的需要填入表格的新值在填写当前一行数据的同时更新数组 L已经遍历过的部分后面不再用到为当前行的数据相当于把当前行的数据逐步填入 L这样在填写下一行数据时L也已经更新为新的参照行。最后得到的 ans 就相当于原表格最右下角的位置即为最终答案。 改进后的代码如下
# include iostreamusing namespace std;const int maxn 1e5 10;
int n;
int A[maxn];
int B[maxn];
int L[maxn];int main()
{cin n;for (int i 1; i n; i) {cin A[i];}for (int i 1; i n; i) {cin B[i];}int ans 0, t;for (int i 1; i n; i) {ans 0;for (int j 1; j n; j) {t ans; //提前记录上一个ans的值if (A[i] B[j]) {ans L[j - 1] 1;}else {ans max(ans, L[j]);}//对已经遍历过的地方将L更新为下一行的值L[j - 1] t; }L[n] ans; }//运行到最后ans便是原二维数组最右下角的结果cout ans endl;return 0;
}
方法2和方法1算法思想基本一致时间复杂度也都是 O(n^2)但方法2的空间复杂度只有 O(n)显然是方法2更胜一筹当然某一问题所需要的空间不大时我们还是优先选择方法1因为方法1写起来更简便。
但上述两种做法时间复杂度都是 O(n^2)。遇到某些对时间限制比较高的情况就不适用了所以我们又提出了下面一种方法。 方法3巧用另一种动态规划
上面解决最长公共子序列问题的算法可简称为LCS。我们还有另一种巧妙的方法来解决这类问题就是将LCS转化为LIS。什么是LIS呢LIS是解决最长递增或不下降子序列的算法。LIS算法的核心思想也是动态规划。我们先来讲讲转化的过程
能够转化的前提是序列A和序列B的数据范围必须相同
我们仍以 3 2 1 4 5 和 1 2 3 4 5 为例 A: 3 2 1 4 5
B: 1 2 3 4 5
我们把A中的数据按顺序变成1、2、3、4、5变成递增顺序即3 - 12 - 21 - 34 - 45 - 5然后B按照A的转化规则进行转化于是变成
A: 1 2 3 4 5 B: 3 2 1 4 5
这样标号之后序列的长度显然不会改变。但是出现了一个性质两个序列的子序列一定是A的子序列。而A本身就是递增的因此这个子序列是递增的。换句话说只要这个子序列在B中递增它就是A的子序列。于是问题就转化成了求B中的最长递增子序列。
你可能觉得这样的转化多此一举但请注意解决最长递增子序列类问题时间复杂度最低可以达到 O(nlogn)也就是说用这种方法我们可以将求解最长公共子序列问题的时间复杂度降为O(nlogn)这样在处理相关问题时就可以避免时间超限的情况。
但新的问题又来了怎么在O(nlogn)时间复杂度内求解最长递增子序列问题这里我参考了别人给出的一个解释
我们以数列 5 2 3 1 4 为例
首先把 5 加入答案序列中然后遍历到 2发现 25 , 于是我们用2替换5然后加3发现32所以直接把3加到答案序列中这时候就是 [2,3] ;然后遍历到1我们发现13于是我们找到一个最小的但是比1大的数字2然后把1替换2为什么这么做不会影响结果呢你可以这么想我们当前已经求出了一个当前最优的序列如果我们用1替换2然后后面来一个数字替换了3那么我们就可以得到一个更优的序列而如果没有数字替换3那么这个1替换2也就是没有贡献的不会影响我们结果的最优性。另外解题时可以直接使用STL的lower_bound函数来找到一个最小的但是大于某个数字的数。 代码如下
# include iostream
# include vector
# include mapusing namespace std;const int maxn 1e5 10;
int n;
mapint, intm;
int B[maxn];int main()
{cin n;int a;for (int i 1; i n; i) {cin a;m[a] i;}int b;for (int i 1; i n; i) {cin b;//按照A的转化规则转化BB[i] m[b];}//序列C用于保存当前的最优解vectorintC;C.push_back(0);int len 0; //保存最终结果for (int i 1; i n; i) {if (B[i] C[len]) {C.push_back(B[i]);len;}else {C[lower_bound(C.begin(), C.end(), B[i]) - C.begin()] B[i];}}cout len endl;return 0;
}
用这种方法时间复杂度就降为O(nlogn)了。我上面给出的那一道题也只有采用这种方法才不会时间超限。而前两种只能得一半的分。 总结
这里我给出了解决最长公共子序列的三种方法大家可以根据实际问题各取所需。以上便是我的看法很高兴与大家分享。
