一、前言

“

有人问我：快毕业了，选择实习呢还是考研呢 ？
  我也干了十年程序了，简单说下我的看法：如果你很喜欢读书，又不是急着用钱，那就考吧！如果不喜欢读书，或者急着用钱，赶紧工作！
  考研后的确更大概率能找到一份更好的工作，但是你工作的这两年如果用心经营，可能收获的远不止这一张文凭这么简单。最重要的是不断学习，不断挖掘自己的上限，规划好自己的五年计划，十年计划，那么无论是在考场上还是职场上，你都能够如鱼得水，平步青云！

”

二、最长公共子序列的定义

1、最长公共子序列的概述

• 最长公共子序列（Longest Common Subsequence）问题是一个经典的计算机科学问题，在生物信息学、分子生物学、数据挖掘、模式识别、文本检索等领域有着重要应用。最长公共子序列问题可分为双序列最长公共子序列问题（简称 LCS）和多序列最长公共子序列问题（简称 MLCS）。
• 本文将介绍双序列的最长公共子序列的动态规划解法，并且在一定程度上进行时间和空间上的优化。

1）版本管理

• 最初对 LCS 问题的研究是将它作为一种增量压缩算法来研究的。
• 例如，在 svn / git 版本管理系统中，文件经过不断迭代修改产生不同的版本，文件本身可能很大，而修改的内容可能很少。为了节省存储空间，我们不必将原始文件和修改文件单独存储，而只需要存储一个基础量 和 一个增量。两个文件版本的比较就类似于 LCS 问题。

2）基因工程

• LCS 算法还可用在基因工程领域。
• 例如，确定一种致病基因的基本方法就是将该疾病患者的 DNA 链与健康者的 DNA 链相比较，找出其中的相同部分与不同部分进行分析。这种基因链的比较也可以用 LCS 算法来解决。

2、最长公共子序列的定义

1）子序列

• 子序列（Subsequence）：给定 个元素的数组序列 ，当下标序列满足 时， 是原序列的子序列。
• 因为每个元素可以选择 "取" 或 "不取"，所以总共有 个子序列。

2）公共子序列

• 公共子序列（Common Subsequence）：给定两个数组序列 和 ，那么对于某个 数组的子序列，同时又是 数组的子序列，则称它为两个序列的公共子序列。

3）最长公共子序列

• 最长公共子序列（Longest Common Subsequence）：给定两个数组序列 和 ，能够找到的元素个数最多的公共子序列被称为这两个序列的最长公共子序列。

三、最长公共子序列的求解

“

【例题1】给定两个数组序列 和 ，其中 ，求两个数组的最长公共子序列。

”

• 最长公共子序列的求解采用的是动态规划，所以首先还是状态的设计。

1、设计状态

• 考虑两个数组序列 和 ，对于 序列中第 个元素 和 序列中的第 个元素 ，有两种情况：

1）相等的情况

• 相等即 的情况，这个时候如果前缀序列 和 的最长公共子序列已经求出来了，记为 的话，那么很显然，在两个序列分别加入 和 以后，长度又贡献了 1，所以 和 的最长公共子序列就是 ； 图三-1-1

2）不相等的情况

• 不相等即 的情况，这个时候我们可以把问题拆分成两个更小的子问题，即 分别去掉 和 的情况，如图三-1-2所示： 图三-1-2
• 去掉 以后，问题转变为求： 和 的最长公共子序列；
• 去掉 以后，问题转变为求： 和 的最长公共子序列；

3）定义状态

• 根据上面的两种情况的讨论，我们发现，在任何时候，我们都在求 的前缀 和 的前缀的最长公共序列，所以可以这么定义状态：用 表示 和 的最长公共子序列。

2、状态转移方程

• 在设计状态的过程中，我们已经无形中把状态转移也设计好了，状态转移方程如下：
• 对于 或者 代表的是：其中一个序列的长度为 0，那么最长公共子序列的长度肯定就是 0 了；
• 其余两种情况，就是我们上文提到的 和 "相等" 与 "不相等" 的两种情况下的状态转移；
• 如图三-2-1所示，代表了字符串 "GATCGTGAGC" 和 "AGTACG" 求解最长公共子序列的 的矩阵。 图三-2-1

3、时间复杂度分析

• 对于长度分别为 和 的两个序列，求解它们的最长公共子序列时，状态数总共有 个，每次状态转移的消耗为 ，所以总的时间复杂度为 。

四、最长公共子序列的优化

1、空间复杂度

• 对于 这个状态，求解过程中，只依赖于 、 、 。
• 即每次求解只需要有 上一行 和 这一行 的状态即可，所以可以采用滚动数组进行优化，将状态转移方程变成：
• 只需要简单将 替换成 ， 替换成 即可。
• 这样就把原本 的空间复杂度变成了 ，其中 。
• 优化后的 c++ 代码实现如下：

typedef char ValueType;
const int maxn = 5010;
int f[2][maxn];

int getLCSLength(int hsize, ValueType *h, int vsize, ValueType *v) {
    memset(f, 0, sizeof(f));
    int cur = 1, last = 0;
    for (int i = 1; i <= vsize; ++i) {
        for (int j = 1; j <= hsize; ++j) {
            if (v[i] == h[j])
                f[cur][j] = f[last][j - 1] + 1;
            else
                f[cur][j] = max(f[cur][j - 1], f[last][j]);
        }
        swap(last, cur);
    }
    return f[last][hsize];
}

2、时间复杂度

“

【例题2】给定两个数组序列 和 ，保证 数组中重复元素的个数不会超过 10 个，其中 ，求两个数组的最长公共子序列的长度。

”

• 由于 ，所以朴素的 算法在这个问题上不再适用。
• 但是，基于上述问题的特殊性，我们可以对朴素求解最长递增子序列问题进行一定优化。特殊性在于： 数组中重复元素个数不会超过 10 个。
• 我们可以考虑的更加极限一点，如果 数组中所有元素都不重复，那么我们只要将 数组中每个元素去 数组中找，找到后连一条线，问题就转变成求最多的不相交线段了。如图四-2-1所示： 图四-2-1
• 实现的时候，可以生成一个辅助数组 ， 数组中的每个元素   是 在 数组中元素的下标，即：
• 如图四-2-2所示，下标从 1 开始，这一步可以通过离散化来实现。

• 要保证线段不相交，其实就是不出现交叉，说得更加通俗一点，就是 数组中的元素值要单调递增，那么问题就转变成了求 数组的 最长递增子序列 的问题了。
• 然后再来考虑 数组中有重复元素的情况，这时我们在生成 数组的时候，一个 有可能对应多个 数组中的下标，即还是用相同方法生成 数组，只是 可能会生成多个 ，并且要求它们按照原本在 数组中的下标逆序排列。
• 生成的 数组中如果重复元素最多 10 个，那么 数组最多有 10n 个元素，剩下的就是求最长递增子序列的过程了，时间复杂度 。
• 基于这类问题的特殊性，算法时间复杂度可以从 优化为 ，如果没有重复元素个数的限制，比如有 个完全一样的元素时，时间复杂度会退化成 ，。

五、最长公共子序列的应用

1、带权最长公共子序列

“

【例题3】给定两个数组序列 和 ，其中 ，求两个数组的公共子序列的最大权值和，权值和定义为公共子序列中每个元素值的和。

”

• 这个问题只需要将状态转移方程稍微做些修改即可：
• 即将原状态转移方程中的 替换成 。

2、路径回溯

“

【例题4】给定两个数组序列 和 ，其中 ，求两个数组的最长公共子序列。

”

• 在计算 数组的值时，同样可以用另一个数组 来记录当前状态是从哪个转移过来的， 然后计算完所有状态后从 迭代求出路径，如图五-2-1所示： 图五-2-1
• c++ 代码实现如下：

int pack(int x, int y) {                              // 1）
    return x * maxn + y;                             
}

int getLCSLength(int hsize, ValueType *h, int vsize, ValueType *v, stack<int>& path) {
    memset(f, 0, sizeof(f));
    while (!path.empty())                             // 2）
        path.pop();
    int cur = 1, last = 0;
    for (int i = 1; i <= vsize; ++i) {
        for (int j = 1; j <= hsize; ++j) {
            if (v[i] == h[j]) {
                f[cur][j] = f[last][j - 1] + 1;
                p[i][j] = pack(i - 1, j - 1);         // 3）
            }
            else {
                f[cur][j] = max(f[last][j], f[cur][j - 1]);
                p[i][j] = f[last][j] > f[cur][j - 1] ? pack(i - 1, j) : pack(i, j - 1);
            }
        }
        swap(last, cur);
    }
    int vidx = vsize, hidx = hsize;
    while (vidx && hidx) {                        
        int pre = p[vidx][hidx];
        int previdx = pre / maxn;
        int prehidx = pre % maxn;
        if (vidx - previdx && prehidx - hidx) {      // 4）
            path.push(vidx * maxn + hidx);
        }
        vidx = previdx;
        hidx = prehidx;
    }
    return f[last][hsize];
}

• 1） pack(int x, int y)函数用来将两个整数打包成一个，方便存储；
• 2）因为路径是逆序求解的，所以可以用一个栈来记录路径；
• 3）计算状态时，同时记录下状态转移的来源；
• 4）这一步是最关键的一步：通过不断迭代，存下最长公共子序列在两个序列的下标位置，只有当两个状态的曼哈顿距离为 2 的时候，才是两个序列中元素相等的情况。

3、公共子序列方案数

“

【例题4】给定两个数组序列 和 ，其中 ，求两个序列的公共子序列的数量。

”

• 假设 "恰好" 以   和 结尾的公共序列的数量为 ，则容易得出状态转移方程如下：
• 这里涉及到了一个 单点更新，矩阵求和，那么我们联想到了二维树状数组，直接二层循环求解 即可，时间复杂度为 。有关树状数组的内容请参考文末的链接。

4、最长公共递增子序列

“

【例题5】给定两个数组序列 和 ，其中 ，求两个序列的最长公共递增子序列，即求出的最长公共子序列的元素随着下标单调递增。

”

• 用 表示 和 两个序列，"恰好" 以 作为最后一个元素的最长公共递增子序列的长度；
• 考虑两种情况：
• 1）当 时， 的 "加入" 和 "不加入" 不影响结果，所以有： ；
• 2）当 时，则需要在   中找出一个满足小于 的状态进行状态转移，即：
• 这样设计的算法，状态总数为 ，状态转移为 ，所以总的求解时间复杂度为 。
• 这里介绍一种优化方案，同时也是其它类似 的动态规划问题转为 时间复杂度的常用手段。核心思路是将状态转移从原先的 变成 。
• 我们首先保证枚举顺序一定是 在外层循环， 在内层循环，那么在计算 的时候，我们希望能够把 事先求出来；
• 可以用一个变量 来记录，即在枚举 时，初始化 ；
• 如果 ，则令 ；
• 如果 ，则 ；
• 最后的答案就是 ；

• 最长公共子序列的相关问题到这里就结束了，如果还有不懂的问题可以留言告诉作者。

• 本文所有示例代码均可在以下 github 上找到：github.com/WhereIsHeroFrom/Code_Templates