08-问题分析

4.3.1　问题分析

给定两个序列X={x₁，x₂，x₃，…，x_m}和Y={y₁，y₂，y₃，…，y_n}，找出X和Y的一个最长的公共子序列。

例如：X=（A，B，C，B，A，D，B），Y=（B，C，B，A，A，C），那么最长公共子序列是B，C，B，A。

如何找到最长公共子序列呢？

如果使用暴力搜索方法，需要穷举X的所有子序列，检查每个子序列是否也是Y的子序列，记录找到的最长公共子序列。X的子序列有2^m个，因此暴力求解的方法时间复杂度为指数阶，这是我们避之不及的爆炸性时间复杂度。

那么能不能用动态规划算法呢？

下面分析该问题是否具有最优子结构性质。

（1）分析最优解的结构特征

假设已经知道Z_k={z₁，z₂，z₃，…，z_k}是X_m={x₁，x₂，x₃，…，x_m}和Y_n={y₁，y₂，y₃，…，y_n}的最长公共子序列。这个假设很重要，我们都是这样假设已经知道了最优解。

那么可以分3种情况讨论。

• x_m= y_n= z_k：那么Z_k−1={z₁，z₂，z₃，…，z_k−1}是X_m−1和Y_n−1的最长公共子序列，如图4-4所示。

图4-4　最长公共子序列

反证法证明 ： 如果Z_k−1={z₁，z₂，z₃，…，z_k−1}不是X_m−1和Y_n−1的最长公共子序列，那么它们一定存在一个最长公共子序列。设M为X_m−1和Y_n−1的最长公共子序列，M的长度大于Z_k−1的长度，即|M|>|Z_k−1|。如果在X_m−1和Y_n−1的后面添加一个相同的字符x_m= y_n，则z_k=x_m=y_n，|M+{z_k}|>|Z_k−1+{z_k}|=|Z_k|，那么Z_k不是X_m和Y_n的最长公共子序列，这与假设Z_k是X_m和Y_n的最长公共子序列矛盾，问题得证。

• x_m≠y_n，x_m≠ z_k：我们可以把x_m去掉，那么Z_k是X_m−1和Y_n的最长公共子序列，如图4-5所示。

图4-5　最长公共子序列

反证法证明： 如果Z_k不是X_m−1和Y_n的最长公共子序列，那么它们一定存在一个最长公共子序列。设M为X_m−1和Y_n的最长公共子序列，M的长度大于Z_k的长度，即|M|>|Z_k|。如果我们在X_m−1的后面添加一个字符x_m，那么M也是X_m和Y_n的最长公共子序列，因为|M|>|Z_k|，那么Z_k不是X_m和Y_n的最长公共子序列，这与假设Z_k是X_m和Y_n的最长公共子序列矛盾，问题得证。

• x_m≠y_n，y_n≠ z_k：我们可以把y_n去掉，那么Z_k是X_m和Y_n−1的最长公共子序列，如图4-6所示。

图4-6　最长公共子序列

反证法证明： 如果Z_k不是X_m和Y_n−1的最长公共子序列，那么它们一定存在一个最长公共子序列。设M为X_m和Y_n−1的最长公共子序列，M的长度大于Z_k的长度，即|M|>|Z_k|。如果我们在Y_n−1的后面添加一个字符y_n，那么M也是X_m和Y_n的最长公共子序列，因为|M|>|Z_k|，那么Z_k不是X_m和Y_n的最长公共子序列，这与假设Z_k是X_m和Y_n的最长公共子序列矛盾，问题得证。

（2）建立最优值的递归式。

设c[i][j]表示X_i和Y_j的最长公共子序列长度。

• x_m= y_n= z_k：那么c[i][j]= c[i−1][j−1]+1；
• x_m≠y_n：那么我们只需要求解X_i和Y_j−1的最长公共子序列和X_i−1和Y_j的最长公共子序列，比较它们的长度哪一个更大，就取哪一个值。即c[i][j]= max{c[i][j−1], c[i−1][j]}。
• 最长公共子序列长度递归式：

（3）底向上计算最优值，并记录最优值和最优策略

i=1时：{x₁}和{y₁，y₂，y₃，…，y_n}中的字符一一比较，按递归式求解并记录最长公共子序列长度。

i=2时：{x₂}和{y₁，y₂，y₃，…，y_n}中的字符一一比较，按递归式求解并记录最长公共子序列长度。

……

i=m时：{x_m}和{y₁，y₂，y₃，…，y_n}中的字符一一比较，按递归式求解并记录最长公共子序列长度。

（4）构造最优解

上面的求解过程只是得到了最长公共子序列长度，并不知道最长公共子序列是什么，那怎么办呢？

例如，现在已经求出c[m][n]=5，表示X_m和Y_n的最长公共子序列长度是5，那么这个5是怎么得到的呢？我们可以反向追踪5是从哪里来的。根据递推式，有如下情况。

x_i= y_j时：c[i][j]= c[i−1][j−1]+1；

x_i≠y_j时：c[i][j]= max{c[i][j−1], c[i−1][j]}；

那么c[i][j]的来源一共有3个：c[i][j]= c[i−1][j−1]+1，c[i][j]= c[i][j−1]，c[i][j]= c[i−1][j]。在第3步自底向上计算最优值时，用一个辅助数组b [i][j]记录这3个来源：

c[i][j]= c[i−1][j−1]+1，b[i][j]=1；

c[i][j]= c[i][j−1]，b[i][j]=2；

c[i][j]= c[i−1][j]，b[i][j]=3。

这样就可以根据b[m][n]反向追踪最长公共子序列，当b[i][j]=1时，输出x_i；当b [i][j]=2时，追踪c[i][j−1]；当b[i][j]=3时，追踪c[i−1][j]，直到i=0或j=0停止。