一、一个基本的模式——LCS问题

LCS（最长公共子序列）问题可以简单地描述如下：

一个给定序列的子序列是在该序列中删去若干元素后得到的序列。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。例如，若X={A，B，C，B，D，B，A}，Y={B，D，C，A，B，A}，则序列{B，C，A}是X和Y的一个公共子序列，但它不是X和Y的一个最长公共子序列。序列{B，C，B，A}也是X和Y的一个公共子序列，它的长度为4，而且它是X和Y的一个最长公共子序列，因为X和Y没有长度大于4的公共子序列。

最长公共子序列问题就是给定两个序列X={x1,x2,...xm}和Y={y1,y2,...yn}，找出X和Y的一个最长公共子序列。对于这个问题比较容易想到的算法是穷举，对X的所有子序列，检查它是否也是Y的子序列，从而确定它是否为X和Y的公共子序列，并且在检查过程中记录最长的公共子序列。X的所有子序列都检查过后即可求出X和Y的最长公共子序列。X的每个子序列相应于下标集{1,2,...,m}的一个子集。因此，共有2^m个不同子序列，从而穷举搜索法需要指数时间。

事实上，最长公共子序列问题具有最优子结构性质：

设序列X={x1,x2,...,xm}和Y={y1,y2,...,yn}的一个最长公共子序列为Z={z1,z2,...,zk}，则

通过以上的结论，我们观察到——两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列，这为我们将算法的时间复杂度降低到多项式级别埋下了伏笔，因为这两个序列的不同的前缀组合只有O(mn)个。并且，根据以上结论，我们可以得出计算Xi和Yj的最长公共子序列的长度c[i][j]的公式:

当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]}。

这样一来，解决这个问题就比较容易了，通过建立递推结构，可以得出下列算法：

X和Y的最长公共子序列的长度就存于c[m][n]中，欲求出具体的子序列，则可通过数组的值用O(m+n)的时间回推，具体的方法不再赘述。

二、小例子——模范丈夫的购物花费

LCS问题具有动态规划的公共特点，即通过找到一种描述，使原问题可以拆解为多项式级的子问题，而它的特色在于，运用串的前缀来做为抽象子问题的基点。下面我们来看一个小例子，这个例子的原型是2002年ACM_ICPC的South America分赛区最后一题。（原题可参见http://acm.zju.edu.cn/show_problem.php?pid=1524）

Jones先生是一位模范丈夫，每个星期六的早晨他的太太都会给它一个购物清单，他只能购买清单上所列的物品并且必须全部买齐。最开始，Jones先生总是穿梭于商店的过道之间，对每样商品选择最便宜的价格购买，但是他逐渐地厌倦了这种方式，并开始了一种新的尝试——对于商店中的每条过道只走一遍，并严格按照清单上物品的顺序购物。现在你要写一个程序来帮助他购物。你所拥有的信息除了清单所列的物品之外，还包括在他选择的整条路线上依次出现的商品和它的价格，你的任务是计算他购齐所有货物的最小花费。

举个例子，如下图所示，Jones需要购买的货物标号依次是1,1,2,20,他必须从右表中依次选择这四样物品，并使总花费最小（在某些情况下，他也可能根本无法找到一种方案购全所有商品），在这个例子中，他的最小花费是21.30元，即选择0.30元和1元的1号商品，然后选择10元的2号和20号商品。

由于Jones先生必须严格的按照清单的顺序购物，并且必须按照规定的路线逛商场，这个问题便具有了运用串的前缀来做为抽象子问题基点的条件。

问题的抽象模式与LCS问题可谓大同小异，需要注意的是，LCS问题为了从长度结果倒推具体的最长公共子序列，将中间子问题的结果存储在了二维数组中，如果我们只需要求问题的一个数值结果，则可以通过迭代的方式来进行从而节省空间消耗。如下所示的程序便展示了这一点，设清单上有m个物品，商店指定路线上有n件商品，物品号存储于一维整数数组goods中，则我们每从输入流in获取一个商品的信息，便可以进行一步递推，并用buy1和buy2两个浮点型一维数组来交替存储结果。最后只要用一个浮点型指针p根据规模参数的奇偶性做简单的定向便可将描述结果的形式统一了。如果最后的p[m]仍为-1，则表示根本无法找到一种方案购全所有商品。

三、思考题——基因函数问题

下面再举一个类似的小例子，它很有趣但并不算很难，请读者自行思考该如何用LCS问题的思维方式解决这个问题。如果您一旦有了想法可以发贴在文章的“评注”里，和我们一起讨论。这个例子的原型是2001年ACM_ICPC的Taejon分赛区第4题。 （原题可参见（http://acm.zju.edu.cn/show_problem.php?pid=1027）

大家都知道人类的基因可以被描述为一个只包含A,C,G,T的序列，生物学家非常乐于在识别人类的基因并确定其功能上下功夫，因为这些可以帮助诊断病人并研制新的药物。通常，一旦一段基因被确定后，接下来的工作便是确定它的功能，这个工作一般是通过搜索数据库来进行的。数据库中存储了很多基因序列及其相应的功能，将返回与新基因序列功能相似的已知序列。

那么如何确定两个基因序列的相似性呢，这主要是通过相似性函数来判断的。比如已知两个序列AGTGATG和GTTAG，他们有多相似？一个判断的方法是在两个序列中分别插入若干空格使得两序列的长度相等，然后通过一个分数矩阵来得出一个数，所有方案的函数值的最大值便代表了新基因序列与旧基因序列的相似程度。比如，我们在第一个序列中插入一个空格，在第二个序列中插入三个空格，得到两个串：

然后，我们根据下表计算每个对应字符的函数值：

因此，这种匹配的函数值是(-3)+5+5+(-2)+(-3)+5+(-3)+5=9。（*表示不能出现空格和空格对应）

我们还可以列出很多种在两个基因序列中插入空格的方法，比如：

这种方式使得函数值是(-3)+5+5+(-2)+5+(-1)+5=14，实际上这是这两个序列所能组成的最大值，因此我们就说这两个基因序列的相似度是14。

我们的问题是，任意给定两个基因段，如何求出它们的相似度呢？请读者思考。