《算法导论》读书笔记与习题解答 — 15.4 最长公共子序列

笔记

　　最长公共子序列（Longest-Common-Subsequence, LCS）问题：给定两个序列Xm=<x1,x2,…,xm>$X_m=<x_1,x_2,\dots ,x_m>$和Yn=<y1,y2,…,yn>$Y_n=<y_1,y_2,\dots ,y_n>$，求解长度最长的公共子序列。

　　如果用暴力搜索法求解LCS问题，就要穷举Xm$X_m$的所有子序列，对每个子序列检查它是否也是Yn$Y_n$的子序列，再从中找到最长子序列。而Xm$X_m$一共有2m$2^m$个子序列（Xm$X_m$的每个元素都可选择在或者不在子序列中，因此子序列有2m$2^m$个），因此暴力搜索法的运行时间为指数级。
　　
　　然而，LCS问题具有最优子结构，可以用动态规划方法来求解。令Z=<z1,z2,…,zk>$Z=<z_1,z_2,\dots ,z_k>$为X$X$和Y$Y$的任意LCS，以下分3种情况：　　
　　(1) 如果xm=yn$x_m=y_n$，则zk=xm=yn$z_k=x_m=y_n$，且Zk−1=<z1,z2,…,zk−1>$Z_{k-1}=<z_1,z_2,\dots ,z_{k-1}>$是Xm−1=<x1,x2,…,xm−1>$X_{m-1}=<x_1,x_2,\dots ,x_{m-1}>$和Yn−1=<y1,y2,…,yn−1>$Y_{n-1}=<y_1,y_2,\dots ,y_{n-1}>$的一个LCS；　　
　　(2) 如果xm≠yn$x_m\ne y_n$，那么zk≠xm$z_k\ne x_m$意味着Zk$Z_k$是Xm−1$X_{m-1}$和Yn$Y_n$的一个LCS；
　　(3) 如果xm≠yn$x_m\ne y_n$，那么zk≠yn$z_k\ne y_n$意味着Zk$Z_k$是Xm$X_m$和Yn−1$Y_{n-1}$的一个LCS。

　　根据以上事实，可以递归地求解LCS问题。如果xm=yn$x_m=y_n$，递归求解Xm−1$X_{m-1}$和Yn−1$Y_{n-1}$的LCS，将xm$x_m$加到Xm−1$X_{m-1}$和Yn−1$Y_{n-1}$的LCS末尾，就得到Xm$X_m$和Yn$Y_n$的LCS。如果xm≠yn$x_m\ne y_n$，则必须求解两个子问题：Xm−1$X_{m-1}$和Yn$Y_n$的LCS、Xm$X_m$和Yn−1$Y_{n-1}$的LCS。二者中较长者即为Xm$X_m$和Yn$Y_n$的LCS。

　　我们用c[i,j]$c[i,j]$表示Xi$X_i$和Yj$Y_j$的LCS长度。根据以上分析，可以得到下面的递归式。

　　根据上式中i$i$和j$j$的取值范围，我们可以知道LCS问题一共有Θ(mn)$\Theta (mn)$个不同的子问题。并且求解规模较大的子问题依赖于规模较小的子问题。因此，可以用动态规划方法自下而上地求解LCS问题。下面给出代码。　　
　　
　　显然，该算法的运行时间为Θ(mn)$\Theta (mn)$，因为每个表项的计算时间为Θ(1)$\Theta (1)$。根据表格b$b$可以构造Xm$X_m$和Yn$Y_n$的LCS。只需从b[m,n]$b[m,n]$开始，并按箭头方向追踪下去即可。代码如下所示。
　　

习题

15.4-1 求<1, 0, 0, 1, 0, 1, 0, 1>和<0, 1, 0, 1, 1, 0, 1, 1, 0>的一个LCS。
　　解
　　LCS为<1, 0, 0, 1, 1, 0>。

15.4-2 设计伪代码，利用完整的表c$c$及原始序列X=<x1,x2,…,xm>$X=<x_1,x_2,\dots ,x_m>$和Y=<y1,y2,…,yn>$Y=<y_1,y_2,\dots ,y_n>$来重构LCS，要求运行时间为O(m+n)$O(m+n)$，不能使用表b$b$。
　　解
　　
15.4-3 设计LCS-LENGTH的带备忘的版本，运行时间为O(mn)$O(mn)$。
　　解
　　
15.4-4 说明如何只使用表c$c$中2×min(m,n)$2\times min(m,n)$个表项及O(1)$O(1)$的额外空间来计算LCS的长度。然后说明如何只用min(m,n)$min(m,n)$个表项及O(1)$O(1)$的额外空间完成相同的工作。
　　解
　　代码一逐行计算表c$c$，在计算c$c$的每一行时，仅需要引用上一行的数据。因此，仅需要两行，一行存储表c$c$的当前行的数据，另一行存储表c$c$的上一行的数据。在代码一中，表c$c$的一行有n$n$个元素，其实可以交换原始序列X$X$和Y$Y$的顺序，这样表c$c$的一行有m$m$个元素。我们在创建表c$c$时，可以选取m$m$和n$n$中的较小值作为表c$c$的一行的元素个数。因此，计算LCS的长度，可以只使用2×min(m,n)$2\times min(m,n)$个表项及O(1)$O(1)$的额外空间。

　　我们再仔细看看代码一，在计算表c$c$的某一个表项c[i,j]$c[i,j]$时，仅需要引用c[i−1,j−1]$c[i-1,j-1]$、c[i−1,j]$c[i-1,j]$和c[i,j−1]$c[i,j-1]$。假设存储空间只有一行。我们是按照从左到右的顺序来计算一行的表项，当计算到c[i,j]$c[i,j]$时，c[i,j]$c[i,j]$的位置上还保留了上一行相同位置的数据c[i−1,j]$c[i-1,j]$，而c[i,j−1]$c[i,j-1]$在c[i,j]$c[i,j]$之前已经被计算得到。现在只剩下c[i−1,j−1]$c[i-1,j-1]$，可以额外用一个变量t$t$来保存c[i−1,j−1]$c[i-1,j-1]$。这样，计算LCS的长度，仅需要表c$c$的一行的空间及O(1)$O(1)$的额外空间。下面只给出这种做法的伪代码。
　　
15.4-5 设计一个O(n2)$O(n^2)$时间的算法，求一个n$n$个数的序列的最长单调递增子序列。
　　解
　　先对数组排序，然后找出排序后的数组与原数组的LCS，就是最长单调递增子序列。简单的插入排序需要O(n2)$O(n^2)$时间，找LCS也需要花费O(n2)$O(n^2)$时间，因此该算法总的运行时间为O(n2)$O(n^2)$。
　　
15.4-6 设计一个O(nlgn)$O(n\text{lg}n)$时间的算法，求一个n$n$个数的序列的最长单调递增子序列。（提示：注意到，一个长度为i$i$的候选子序列的尾元素至少不比一个长度为i−1$i-1$的候选子序列的尾元素小。因此，可以在输入序列中将候选子序列链接起来。）
　　解
　　假设原数列为X$X$。我们用e[i]$e[i]$表示以元素X[i]$X[i]$结尾的最长单调递增子序列（Longest Monotonically Increasing Sub-sequence，LMIS）的长度。为了计算每个元素的e[i]$e[i]$，我们需要维护一个有序数组S$S$。依次遍历原数组X$X$中的每个元素X[i]$X[i]$，在有序数组S$S$中找到不小于X[i]$X[i]$的最小元素，并用X[i]$X[i]$替换它。如果有序数组S$S$中的所有元素都比X[i]$X[i]$小，那么将X[i]$X[i]$放到有序数组S$S$中的最后一个元素的后一个位置。X[i]$X[i]$在有序数组S$S$中的位置就是e[i]$e[i]$。下面用一个例子来说明。　　
　　有一个数组X=<9,1,2,4,6,3,5,0>$X=<9,1,2,4,6,3,5,0>$，下表列出了每次迭代后有序数组S$S$的变化，以及每个元素有e[i]$e[i]$。可以看到，LMIS的长度为4$4$，也就是最大的e[i]$e[i]$。

迭代次数i$i$	元素X[i]$X[i]$	数组S	e[i]$e[i]$
1	9	9　/　/　/　/　/　/　/	1
2	1	1　/　/　/　/　/　/　/	1
3	2	1　2　/　/　/　/　/　/	2
4	4	1　2　4　/　/　/　/　/	3
5	6	1　2　4　6　/　/　/　/	4
6	3	1　2　3　6　/　/　/　/	3
7	5	1　2　3　5　/　/　/　/	4
8	0	0　2　3　5　/　/　/　/	1

　　我们现在来寻找整个数组的LMIS。我们已经知道，LMIS的长度为4$4$。按如下步骤来寻找：
　　1) 先找到e[i]$e[i]$为4$4$的元素，有两个，元素值分别为5$5$和6$6$。以其中一个作为LMIS的尾元素。假设我们选择5$5$作为尾元素，即原数组的第7$7$个元素。
　　2) 接下来我们寻找一个长度为3$3$的单调递增子序列的尾元素。寻找范围是在原数组第1$1$~6$6$个元素之内（因为原数组第7$7$个元素在步骤1$1$)中已被找出，故第7$7$个元素及其后的元素不再考虑），并且找到的元素必须小于步骤1)中找到的元素。满足这些条件的元素有两个，元素值分别为3$3$和4$4$。假设我们选择3$3$作为我们找到的元素，即原数组的第6$6$个元素。
　　3) 接下来我们寻找一个长度为2$2$的单调递增子序列的尾元素，寻找方法与步骤2)一样。我们找到的元素值为2$2$，即原数组的第3$3$个元素。
　　4) 最后我们要寻找一个长度为1$1$的单调递增子序列的尾元素。我们找到的元素为1$1$，即原数组的第2$2$个元素。
　　按以上迭代步骤，我们找到一个完整的LMIS为<1,2,3,5>$<1,2,3,5>$。
　　如果我们在迭代过程中要寻找一个长度为k$k$的单调递增子序列的尾元素，可以采用一种简单的方法。从后向前遍历e[i]$e[i]$，首先遇到的满足e[ik]==k$e[i_k]==k$的元素作为我们找到的元素X[ik]$X[i_k]$。这个元素必定小于上一步迭代过程中找到的长度为k+1$k+1$的单调递增子序列的尾元素X[ik+1]$X[i_{k+1}]$。因为如果不满足X[ik]<X[ik+1]$X[i_k]<X[i_{k+1}]$，那么在将X[ik+1]$X[i_{k+1}]$插入到有序数组S$S$中时，由于X[ik+1]≤X[ik]$X[i_{k+1}]\le X[i_k]$，X[ik+1]$X[i_{k+1}]$会取代X[ik]$X[i_k]$，或者取代X[ik]$X[i_k]$之前的某个元素，那么X[ik+1]$X[i_{k+1}]$就不是一个长度为k+1$k+1$的单调递增子序列的尾元素，这推导出了矛盾。因此X[ik]<X[ik+1]$X[i_k]<X[i_{k+1}]$必然成立。
　　综上所述，我们可以形成一个算法，下面给出了伪代码。
　　
　　下面分析该算法的时间复杂度。LMIS包含一重循环，每次循环迭代会调用一次FIND-POS$\text{FIND-POS}$。而FIND-POS$\text{FIND-POS}$是一个二分查找，它的时间复杂度为O(lgn)$O(\text{lg}n)$。故LMIS的时间复杂度为O(nlgn)$O(n\text{lg}n)$。PRINT-LMIS$\text{PRINT-LMIS}$也只包含一重循环，每次循环迭代为常数时间，故PRINT-LMIS$\text{PRINT-LMIS}$的时间复杂度为O(n)$O(n)$。综上，整个算法的时间复杂度为O(nlgn)$O(n\text{lg}n)$。

　　本节相关的code链接。　
　　https://github.com/yangtzhou2012/Introduction_to_Algorithms_3rd/tree/master/Chapter15/Section_15.4