最长公共子序列O(lgmn)算法
问题描述：
给定两个序列
序列1： C T G A C
序列2： G T A G
求两个序列的最长公共子序列
显然，T G就是一个最长公共子序列
另外，G A和T A也是，最长公共子序列通常不唯一
最长公共子序列(Longest Common Subsequence)为了方便简写成LCS
继续上面的问题，给序列2延长一位X(如下所示)：
序列1： C T G A C
序列2： G T A G X
序列1去掉末尾C与序列2的最长公共子序列为LCS_left
序列1与序列2去掉末尾X的最长公共子序列为LCS_up
序列1去掉末尾C与序列2去掉末尾X的最长公共子序列为LCS’
要求的是序列1与序列2的最长公共子序列LCS
那么有以下两种种情况：
- X和序列1末尾的C相等(X是C)，那么LCS'延长一位C就是LCS。
- X和序列1末尾的C不等(X非C)，那么LCS_left和LCS_up里最长的那个就是LCS。
第一种情况很好理解，就相当于有两个序列，末尾都添加了一样的字符，那么之前的LCS’(T G)延长一位就是现在的LCS(T G C)。
第二种情况可以分开讨论。一种情况是LCS比LCS'更长，那显然是延长了一位，这一位或者是序列1末尾的C( LCS = LCS_up > LCS_left )，或者是序列2末尾的X( LC S= LCS_left > LCS_up )。另一种情况是LCS相比LCS'没有更长，那么LCS’，LCS_up和LCS_left就是相等的(LCS=LCS_up=LCS_left)。可见这两种情况下，让LCS等于LCS_left和LCS_up中大的那个都没问题。
要求LCS显然需要知道LCS’，LCS_up和LCS_left，没错，这就是典型的动态规划算法。创建一个矩阵，用来保存中间结果。
| C | T | G | A | C | |
|---|---|---|---|---|---|
| G | 0 | 0 | 1 |
如同上面的表格所示，横向是序列1，纵向是序列2(只计算都到第一个元素)，表格的值代表比对到这里时，LCS的长度。
表格值上面的值就是LCS_up的长度，同理，左边的值就是LCS_left的长度，左上是LCS'的长度。
现在比对到序列1的G和序列2的G，元素相同，所以当前的值应该是左上LCS'长度的值加一。左上不存在，代表没有LCS’，所以长度是0，0加1等于1。
| C | T | G | A | C | |
|---|---|---|---|---|---|
| G | 0 | 0 | 1 | 1 |
如上表所示，比对到了序列1的A和序列2的G，元素不同，所以左边和上边哪个值大，选大的值填入。上方没有值，所以默认是0，左边是1，左边大，填入左边的值。
这个表格就是得分矩阵D，两个字符串记为X和Y，长度分别是m和n，X(i)代表字符串X的第i个元素，Y(j)同理，D(i, j)代表得分矩阵对应X(i)Y(j)时的值。填表的过程就是计算得分矩阵的过程，根据得分矩阵，就可以找到最长公共子序列。
以上的填表规则可以总结为：
$$D(i, j) = D(i-1, j-1) \quad if X(i) = Y(j)$$
$$D(i, j) = Max(D(i-1, j), D(i, j-1)) \quad if X(i) != Y(j)$$
根据以上公式计算出的完整得分矩阵如下(X = A)：
| C | T | G | A | C | |
|---|---|---|---|---|---|
| G | 0 | 0 | 1 | 1 | 1 |
| T | 0 | 1 | 1 | 1 | 1 |
| A | 0 | 1 | 1 | 2 | 2 |
| G | 0 | 2 | 2 | 2 | 2 |
| A | 0 | 1 | 2 | 3 | 3 |
把矩阵当中相同的数组看作同一个颜色的色块，每个色块的左上方尖角所对应的元素，就是LCS的组成元素。从矩阵的右下方向左上方回溯，从一个尖角找到离他最近的左上方的尖角，直到矩阵左上方。这祖组尖角就是倒序的LCS。
如上所示的矩阵，LCS是T G A。
动态规划的方法求解LCS，就是计算得分矩阵的过程，显然时间复杂度和空间复杂度都是O(lgmn)。而这实际也是目前通用的最好的复杂度，不过再面对一些具体问题的时候也可以做一些优化。
最长递增子序列(LIS)算法
先介绍一个前置问题，最长递增子序列问题。
一个不重复的数字序列(01, 06, 17, 07, 09, 14, 08, 18, 02, 05)，求这个序列最长的增长子序列。
最长递增子序列(Longest Increase Subsequence)简称LIS。
上面序列的LIS是(01, 06, 07, 09, 14, 18)
求解LIS的方法，思想上依然朴实，就是一个一个元素的延长序列，也就是动态规划。
假设序列从1开始，延长到了17，即(01, 06, 17)，显然序列的LIS就是(01, 06, 17)。简单的记录下这个LIS如下。
| 01 | 06 | 17 |
|---|
这时延长一个元素X，如果X比17大，那么新的LIS就是(01, 06, 17, X)，如果X比17小呢？
这个实例当中X是7，考虑之前的序列当中，1和6仍是比7小，所以有了两个等长的LIS，(01, 06, 17)和(01, 06, 07)在上面的表格当中把07写在17的下方。07和17同在第三列表示他们都是各自LIS的第三位，07在17下方，表示07在原序列中的位置比17靠后。
| 01 | 06 | 17 | |||
|---|---|---|---|---|---|
| 07 |
类似的，继续填表。
| 01 | 06 | 17 | |||
|---|---|---|---|---|---|
| 07 | 09 | 14 |
接下来是08，08比07大，所以在第四列，比09晚，所以在09下面，再加一行。
| 01 | 06 | 17 | |||
|---|---|---|---|---|---|
| 07 | 09 | 14 | |||
| 08 |
接下来是18，18比之前最大的14更大，所以排在第六列，又不比08更晚，如果和14同行表示比08早，显然不行，所以要和08同行。
| 01 | 06 | 17 | |||
|---|---|---|---|---|---|
| 07 | 09 | 14 | |||
| 08 | 18 |
剩下的元素依照上述规则继续填入表格，最终结果如下。
| 01 | 06 | 17 | |||
|---|---|---|---|---|---|
| 07 | 09 | 14 | |||
| 08 | 18 | ||||
| 02 | 05 |
从表格的最右列的最下行开始，向左上回溯，只要在当前元素左边和上边的元素都是比当前元素小，且在当前元素之前出现的。从右下到左上，找到一条经过最多列的路径，就是LIS。上面的实例可以得到两条LIS(01, 06, 17或07, 09, 14, 18)。
以上算法需要遍历n(序列长度)个元素，遍历每个元素都需要查找一次元素的位置(时间复杂度O(lgn))，所以时间复杂度是O(nlgn)，如果用十字链表存储元素，空间复杂度是O(n)。
实际上如果只是求LIS的长度，而不需要得到具体的LIS，那么以上矩阵可以压缩成一个数组(一列压缩成一个元素)，每列都只保留最下面的元素就可以了，这也是大多数求LIS长度算法的实现，类似下面这样。
| 01 | 02 | 05 | 08 | 14 | 18 |
|---|
最长公共子序列O(nlgn)算法
我们知道LIS的时间复杂度是O(nlgn)，那么如果能把LCS问题转化为LIS问题，时间LCS的复杂度就是O(nlgn)了。
转化的方法是把序列1中的元素用这个元素在序列2中的位置替换，举个栗子。
序列1： C T G A C
序列2： G T A G
序列1的第一个元素C，不在序列2中，所以忽略。第二个元素T在序列2中的位置是(2),替换。
序列1： null (2) G A C
序列2： G T A G
依此类推
序列1： null (2) (1, 4) (3) null
序列2： G T A G
显然，现在只要求出序列1的LIS，就得到了LCS，但是其中一个限制是每个括号内只能选出一个元素，这样很不方便计算。
一个小技巧是把括号内的数字按从大到小排序，这样就可以保证每个括号内最多只能选出一个元素，也就可以把括号去掉了，最终的替换结果如下。
序列1： 2 4 1 3
序列2： G T A G
求得序列1的LIS结果对应到序列2的顺序就得到了LCS，结果如下。
2 4(T G), 2 3(T A), 1 3(G A)
以上的例子当中，每个序列都只有四种元素(A C G T)，这四种元素的集合就是字母表(alphabet)。上面的算法适合字母表比较大的序列。
举个极端的例子。
序列1： A A A A
序列2： A A A A A
这时序列1的替换就成了长度为nm的序列。
序列1： (5 4 3 2 1) (5 4 3 2 1) (5 4 3 2 1) (5 4 3 2 1)
那么求解的时间复杂度就退化为O(mnlgmn)，大于动态规划的O(mn)。
实际动态规划算法还有更多的灵活应用，因此在生物信息的序列比对领域，依然是最基础的算法。