动态规划-最长公共子序列



一、什么是最长公共子序列

    给定一个序列X=<x1,x2,...xm>,另一个序列Z=<Z1,Z2,...Zk>满足如下条件时称为X的子序列,即存在一个严格递增的下标序列<i1,i2,...ik>,对所有j=1,2,...k,满足Xij=zj.例如，Z=<B,C,D,B>是X=<A,B,C,B,D,A,B>的子序列,对应的下标为<2,3,5,7>。

    最长公共子序列，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。而最长公共子串(要求连续)和最长公共子序列是不同的

    寻找LCS的一种方法是枚举X所有的子序列，然后注意检查是否是Y的子序列，并随时记录发现的最长子序列。假设X有m个元素，则X有2^m个子序列，指数级的时间，对长序列不实际。

二、最优公共子序列的最优子结构

   设X=<x₁,x₂,…,x_m>和Y=<y₁,y₂,…,y_n>为两个序列，LCS(X,Y)表示X和Y的一个最长公共子序列，可以看出

    1、如果x_m=y_n，则LCS ( X,Y ) = x_m + LCS ( X_m-1,Y_n-1 )。

    2、如果x_m!=y_n，则LCS( X,Y ) = max{ LCS ( X_m-1, Y ), LCS ( X, Y_n-1 ) }

    为了找到最长的公共子序列，我们定义C[i][j]表示X_i和Yj的LCS的长度，如果i=0或者j=0,即一个序列的长度为0时，那么LCS的长度为0.根据LCS问题的最优子结构性质，可得到如下公式:

三、算法实现

int lcs_len(char* a, int m, char* b, int n) { int i, j; int dp[MAX_N][MAX_N]; for (i = 0; i < m; i++) dp[i][0] = 0; for (j = 0; j < n; j++) dp[0][j] = 0; for (i = 1; i < m; i++) for (j = 1; j < n; j++) dp[i][j] = (b[j] == a[i]) ? (dp[i-1][j-1] + 1) : max(dp[i][j-1], dp[i-1][j]); return dp[m-1][n-1]; }