动态规划(二)：最长公共子序列(LCS)

LCS：给出两个序列S1和S2，求出的这两个序列的最大公共部分S3就是就是S1和S2的最长公共子序列了。公共部分

必须是以相同的顺序出现，但是不必要是连续的。

解法一：在没学动态规划之前，我能想到的方法就是枚举了。将S1的所有子序列全部检查是否是S2的子序列，从中

选出最长公共子序列。对于长度为n的序列，其子序列共有2的n次方个，这样的话这种算法的时间复杂度就为指数级

了，这显然不太适合用于序列很长的求解了。

解法二：既然学到了动态规划，就来看看能否用动态规划的思想来解决这个问题。要使用动态规划，必须满足两个条

件：有最优子结构和重叠子问题。为了便于学习，我们先来了解下这两个概念。

如果问题的一个最优解中包含了子问题的最优解，则该问题具有最优子结构。当一个递归算法不断地调用同一问题

时，我们说该最优问题包含重叠子问题。

说明：动态规划要求其子问题既要独立又要重叠，这初看上去貌似存在矛盾，其实不然。只是这里说的是两个不同的

概念。独立指的是同一问题的两个子问题不共享资源。而重叠子问题指的是子问题可以作为不同的问题的子问题出

现。

设X = <x1,x2...xm>, Y = <y1,y2...yn>为两个序列，并设Z = <z1,z2...zk>为X和Y的任意一个LCS。可以得出：

1、如果xm = yn，那么zk = xm = yn而且Z(k-1)是X(m-1)和Y(n-1)的一个LCS；

2、如果xm != yn，那么zk != xm蕴含Z是X(m-1)和Y的一个LCS；

3、如果xm != yn，那么zk != yn蕴含Z是X和Y(n-1)的一个LCS。

注：上面的Z(k-1)表示序列Z<z1,z2...zn>,其中n=k-1。其它的X()和Y()也是一样的。

很容易证明上述三点是成立的，详细证明见算法导论。所以LCS具有最优子结构。从上面也可以看出LCS问题中的重

叠子问题的性质。所以我们可以用动态规划来解决LCS问题。由LCS问题的最优子结构可得出递归式：

下面来看看实现代码：

#include<iostream>#include<cstring>using namespace std;int c[100][100]; // c[i][j]表示序列S1前i个元素和S2的前j个元素的LCSint b[100][100]; //便于求解最优解void LCS_Length (char x[], char y[]);void Print_LCS (char x[], int i, int j);int main(){char X[100], Y[100];while (cin >> X >> Y){LCS_Length (X, Y);Print_LCS (X, strlen(X), strlen(Y));cout << endl;}return 0;}void LCS_Length (char x[], char y[]){int m = strlen (x);int n = strlen (y);for (int i = 0; i <= m; i++)c[i][0] = 0;for (int i = 0; i <= n; i++)c[0][i] = 0;for (int i = 0; i < m; i++){for (int j = 0; j < n; j++){if (x[i] == y[j]){c[i + 1][j + 1] = c[i][j] + 1;b[i + 1][j + 1] = 0;}else if (c[i][j + 1] >= c[i + 1][j]){c[i + 1][j + 1] = c[i][j + 1];b[i + 1][j + 1] = 1;}else{c[i + 1][j + 1] = c[i + 1][j];b[i + 1][j + 1] = 2;}}}}void Print_LCS (char x[], int i, int j){if ((i == 0) || (j == 0))return ;if (b[i][j] == 0){Print_LCS (x, i - 1, j - 1);cout << x[i - 1] << ' ';}else if (b[i][j] == 1)Print_LCS (x, i -1, j);elsePrint_LCS (x, i, j - 1);}

书上后面给出了一种可以节省空间的方法，就是不要b数组，直接判断。因为c[i][j]仅依赖于c[i-1][i-1],c[i-1][j],c[i][j-1]。

这样的话只要小小修改下Print_LCS函数即可。