最长公共子序列(LCS)问题
本课程是从少年编程网转载的课程，目标是向中学生详细介绍计算机比赛涉及的编程语言，数据结构和算法。编程学习最好使用计算机，请登陆 www.3dian14.org (免费注册，免费学习)。
本课我们来讨论最长的公共子序列（Longest Common Subsequence，LCS）问题，它也是动态编程的经典问题。
先看一下LCS问题的描述。
给定两个序列，找出两个序列中都存在的最长子序列的长度。子序列是指以相同的相对顺序出现，但不一定是连续的序列。
例如, “abc”, “abg”, “afg”, “bdf”, “aeg”, “acefg”等等都是存在于序列 “abcdefg”中的子序列。
而“ag”, “afc”, “afg”, “fce”, “acefg”, “cefag”等等都是序列“agfcefag”的子序列。
现在需要找出存在于上述两个序列中的公共子序列，并且它的长度是最长的。这里的“acefg”就是最长的LCS，长度为5。
再看两个例子：
1）对于输入序列“ABCDGH”和“AEDFHR”, “ADH”是最长的公共子序列，长度为3。
2）对于输入序列“AGGTAB”和“GXTXAYB”, “GTAB”是最长的公共子序列，长度为4。
这是一个经典的计算机科学问题，它也是diff程序（一种可以比较和输出两个文件的内容差异的程序）的基础，并已在生物信息学中得到应用。
暴力破解法
这个问题的朴素解决方案是暴力破解法：生成两个给定序列的所有子序列，逐个进行比对，找到匹配的公共子序列，并且从中取最长的匹配子序列。
为了找出暴力破解方法的复杂性，我们首先需要知道长度为n的字符串的可能不同子序列的数量，即找到长度为1,2，.. n-1的子序列的数量。
从排列组合理论中可知，
具有1个元素的组合数为
具有2个元素的组合数为
依此类推。我们知道
由于我们不考虑长度为0的子序列，因此长度为n的字符串具有个不同的可能子序列。这意味着暴力破解方案的时间复杂度为
。这里注意，检查一个子序列是否是两个字符串的公共子序列需要
时间。
因此暴力破解方案在时间复杂度方面是指数级的。用动态编程可以改善时间复杂度。
动态编程法-最佳子结构
我们来看看如何采用动态编程解决上述问题。
令输入序列分别保存在为长度为m和n的两个数组X[0..m-1]和Y[0..n-1]中。
并令L(X[0..m-1], Y[0..n-1]) 为两个序列X和Y的LCS的长度。
以下是L(X[0..m-1], Y[0..n-1]) 的递归定义：
1）如果两个序列的最后一个字符都匹配（或X[m-1] == Y[n-1]），则
L(X[0..m-1], Y[0..n-1]) = 1+L(X[0..m-2], Y[0..n-2])
2）如果两个序列的最后一个字符都不匹配（或X [m-1]！= Y [n-1]），则
L(X[0..m-1], Y[0..n-1]) = MAX(L(X[0..m-2], Y[0..n-1]), L(X[0..m-1], Y[0..n-2]))
例子：
1) 考虑输入字符串“AGGTAB”和“GXTXAYB”。两个字符串的最后一个字符“B”相匹配。因此，LCS的长度可以写成：
L(“AGGTAB”，“GXTXAYB”) = 1 + L (“AGGTA”, “GXTXAY”)
这里的1是匹配的字符“B”的长度，L (“AGGTA”, “GXTXAY”)表示去除“B”后剩下的两个新字符串的LCS。
2）考虑输入字符串“ABCDGH”和“AEDFHR”。字符串的最后一个字符不匹配。因此，LCS的长度可以写成：
L(“ABCDGH”, “AEDFHR”) = MAX(L(“ABCDG”, “AEDFHR”)，L(“ABCDGH”, “AEDFH”))
这里L(“ABCDG”, “AEDFHR”)是字符串“ABCDG”取出最后一个字符“H”后，所得到的新字符串“ABCDG” 与原来的另一个字符串“AEDFHR”，再一起求出的LCS。
L(“ABCDGH”, “AEDFH”)是字符串“AEDFHR”取出最后一个字符“R”后，所得到的新字符串“AEDFH” 与原来的另一个字符串“ABCDGH”，再一起求出的LCS。
上述两个LCS值中较大的值就是原有两个字符串的LCS。
下面的图是求L(“AGGTAB”，“GXTXAYB”)的过程示意图（注意是示意图）。
下是LCS问题的简单递归实现, 它遵循上述递归结构。
/* C++程序：上述问题的简单递归实现 */
#include <bits/stdc++.h>
using namespace std;
int max(int a, int b);
/* 返回 X[0..m-1], Y[0..n-1]中的LCS长度 */
int lcs( char *X, char *Y, int m, int n )
{
if (m == 0 || n == 0)
return 0;
if (X[m-1] == Y[n-1])
return 1 + lcs(X, Y, m-1, n-1);
else
return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
}
/* 取出两数字的较大者*/
int max(int a, int b)
{
return (a > b)? a : b;
}
/* 主程序 */
int main()
{
char X[] = "AGGTAB";
char Y[] = "GXTXAYB";
int m = strlen(X);
int n = strlen(Y);
cout<<"Length of LCS is "<< lcs( X, Y, m, n ) ;
return 0;
}
试输入上述程序并运行。
动态编程法-重叠子问题
上述朴素递归方法的时间复杂度在最坏情况下为。最坏情况发生在X和Y的所有字符不匹配（即LCS的长度为0）时。
考虑到以上实现，下面是输入字符串“AXYT”和“AYZX”的部分递归树
在上面的部分递归树中，lcs（“AXY”，“AYZ”）被求解了两次。如果我们绘制完整的递归树，则可以看到有很多子问题可以一次又一次地被重复计算。因此，此问题具有“重叠子结构”属性，可以通过使用“记忆方式”或“列表方式”来避免相同子问题的重新计算。以下是LCS问题的列表方式的实现。
/* 解决LCS的动态编程法 C++代码例子 */
#include<bits/stdc++.h>
using namespace std;
int max(int a, int b);
/* 返回 X[0..m-1], Y[0..n-1]中的LCS长度 */
int lcs( char *X, char *Y, int m, int n )
{
int L[m + 1][n + 1];
int i, j;
/* Following steps build L[m+1][n+1] in
bottom up fashion. Note that L[i][j]
contains length of LCS of X[0..i-1]
and Y[0..j-1] */
/*从下而上构造 L[m+1][n+1]*/
/*L[i][j] 包含X[0..i-1]和Y[0..j-1]的LCS长度*/
for (i = 0; i <= m; i++)
{
for (j = 0; j <= n; j++)
{
if (i == 0 || j == 0)
L[i][j] = 0;
else if (X[i - 1] == Y[j - 1])
L[i][j] = L[i - 1][j - 1] + 1;
else
L[i][j] = max(L[i - 1][j], L[i][j - 1]);
}
}
/*L[m][n] 包含X[0..n-1]和Y[0..m-1]的LCS长度*/
return L[m][n];
}
/* 取出两数字的较大者*/
int max(int a, int b)
{
return (a > b)? a : b;
}
// 主程序
int main()
{
char X[] = "AGGTAB";
char Y[] = "GXTXAYB";
int m = strlen(X);
int n = strlen(Y);
cout << "Length of LCS is "
<< lcs( X, Y, m, n );
return 0;
}
试输入上述程序并运行。
上述实现的时间复杂度为。比朴素递归算法实现的最坏情况下的时间复杂度好得多。