动态规划问题（二）——最长公共子序列

一、问题描述 最长公共子序列(longest common subsequence, LCS)问题：给定两个序列X=(x1, x2, … , xm)和 Y=(y1, y2, … , yn), 求X和Y长度最长的公共子序列。 二、暴力求解方法 蛮力法是解决最长公共子序列问题最容易想到的方法，即对X的每一个子序列，检查是否为Y的子序列，从而确定它 是否为X和Y的公共子序列，并且选出最长的公共子序列。 X和Y的所有子序列都检查过后即可求出X和Y的最长公共子序列。X的一个子序列相应于下标序列1,2，…，m的一个子 序列。因此，X共有2^m个子序列。当然，Y也有2^n个子序列。 因此，蛮力法的时间复杂度为O(2^n * 2^m)，这可是指数级别，绝对不可取！

三、动态规划方法 1.刻画最长公共子序列的特征 ①首先定义前缀的概念：给定一个序列X=(x1, x2, … , xm)，对i=0, 1, … , m, 定义X的第i前缀为 X=(x1, x2, … , xi)。其中X0是空串。 ②LCS的最优子结构： 令X=(x1, x2, … , xm)和Y=(y1, y2, … , yn)为两个序列，Z=(z1, z2, … , zk)为X和Y的任意LCS。 a.如果xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的一个LCS； b.如果xm≠yn，那么zk≠xm意味着Z是Xm-1和Y的一个LCS； c.如果xm≠yn，那么zk≠yn意味着Z是X和Yn-1的一个LCS。

2.一个递归解 定义c[i, j]表示Xi和Yj的LCS长度。如果i=0或j=0，即一个序列长度为0，那么LCS的长度为0。根据LCS问题的最优 子结构性质，有： ①若i=0或j=0, c[i, j]=0; ②若i, j>0且xi=yj，c[i, j]=c[i-1, j-1]+1; ③若i, j>0且xi≠yj，c[i, j]=max(c[i, j-1], c[i-1, j]).

3.C语言实现 (1)计算LCS的长度（最长长度即为c[m][n]）

/* 函数LCSLength接受两个序列(字符串)X=(x1,x2,...,xm)和Y=(y1,y2,...,yn)为输入 定义c[i, j]为X和Y的LCS的长度，c[m+1][n+1]保存了X和Y的LCS的长度 b[i ,j]指向的表项对应c[i ,j]所选择的子问题最优解 */ void LCSLength(char *x, char *y, int m, int n, int **c, int **b) { int i, j; for (i = 1; i <= m; i++) c[i][0] = 0; for (j = 0; j <= n; j++) c[0][j] = 0; for (i = 1; i <= m; i++) { for (j = 1; j <= n; j++) { if (x[i - 1] == y[j - 1]) //若xi=yj, 则c[i, j]=c[i-1, j-1]+1; { c[i][j] = c[i - 1][j - 1] + 1; b[i][j] = 0; //标记为'↖' } else if (c[i - 1][j] >= c[i][j - 1]) //若xi≠yj,c[i, j]=max(c[i, j-1],c[i-1, j]) { c[i][j] = c[i - 1][j]; b[i][j] = 1; //标记为'↑' } else { c[i][j] = c[i][j - 1]; b[i][j] = -1; //标记为'←' } } } }

(2)构造LCS

//构造X和Y的LCS void PrintLCS(int **b, char *x, int i, int j) { if (i == 0 || j == 0) return; if (b[i][j] == 0) //当在表项b[i, j]中遇到一个'↖'时，意味着xi=yj是LCS的一个元素 { PrintLCS(b, x, i - 1, j - 1); printf("%c ", x[i - 1]); } else if (b[i][j] == 1) //按照'↑'方向继续追踪LCS PrintLCS(b, x, i - 1, j); else PrintLCS(b, x, i, j - 1); //按照'←'方向继续追踪LCS }

(3)测试代码

#include"heap.h" #include"LCS.h" #include<stdlib.h> int main() { char *x = "ABCBDAB"; char *y = "BCBA"; int m, n; m = strlen(x); n = strlen(y); int **b = new_heap(m + 1, n + 1); int **c = new_heap(m + 1, n + 1); LCSLength(x, y, m, n, c, b); PrintLCS(b, x, m, n); printf("\n"); delete_heap(b, m + 1); delete_heap(c, m + 1); return 0; }

(4)运行效果

四、总结 过程LCSLength的运行时间为Θ(mn)，因为每个表项的计算时间为Θ(1)。 构造LCS的运行时间为O(m+n)，因为每次递归调用i和j至少有一个会减少1。