C++ 动态规划经典案例解析之最长公共子序列（LCS）_窥探递归和动态规划的一致性

1. 前言

动态规划处理字符相关案例中，求以及求，算是经典中的经典案例。

讲解此类问题的算法在网上一抓应用一大把，即便如此，还是忍不住有写此文的想法。毕竟理解、看懂都不算是真正掌握，唯有瞧出其中玄机，能有自己独有的见解和不一样的感悟方算是把知识学到灵魂深入。

好了！闲话少说，进入正题。

2. 最长公共子序列(LCS)

2.1 问题描述

最长公共子序列，指找出 个或多个字符串中的最长公共子序列。

如字符串 和，其最长公共子序列是。

Tips： 子序列只要求其中字符保持和原字符串中一样的顺序，而不一定连续。

2.2  递归思想

一道求最值的问题，只要是求最值，必然会存在多个选择，原理很简单，如果没有多个选择，还有必要纠结谁是最大谁是最小吗？

Tips： 在你面前有苹果、桔子、香蕉……你只能选择一个，这时候方有纠结。如果面前只有苹果，还会纠结吗？

面对此问题，可以采用化整为零的思想，从宏观层面转移到微观层面，缩小问题的规模的递归思想。

如为字符串设置位置指针 ，为字符串设置位置指针，则问题可以抽象为如下函数。函数的语义：和作为起始位置时字符串的最长公共子序列。

初始时，和意味求解完整的和的最长公共子序列。此时规模最大，无法直接得到答案。如此，把问题延续到规模较小的子问题。

上文说过，求最值一定存在多个选择的，原始问题中的，则可存在如下 种选择：

A、不动，。即把指向作为起始位置的字符串和作为起始位置的字符串继续比较。可算为一个子问题。

B、不动，。即把指向作为起始位置的字符串和作为起始位置的字符串继续比较。可算为另一个子问题。

C、和同时移动到下一个位置。即把指向作为起始位置的字符串和作为起始位置的字符串继续比较。也算为一个子问题。

也就是说，当原始问题中和指向位置字符不相同时，存在 个选择。至于子问题如何求解，这个归功于递归思想。

Tips： 递归最大的好处就是只需要确定基础函数的功能，然后确定子问题，则子问题的内部如何求解站在宏观角度可以不管。反之它可以一步一步继续缩小问题规模，直到有答案为止。

然后在 种选择中，返回值最大的那一个作为当前的问题的结果。

如下图所示，当所指向位置的值相同时，必然在当前子问题中就找到了一个公共字符，则最终结果就是后续子问题的结果基础上加 1 ，则为最长公共子序列为原来的值加 。

Tips： 在海滩上捡贝壳时，当前拾到了一个，回家时最终能拾到的贝壳一定是当前拾到的这一个加上后续所拾到的贝壳。

同时移动 和，进入规模较小的子问题。如下图所示。

此时可总结一下，使用递归求最长公共子序列，类似于玩消消乐，相同，则消掉，直接进入剩下的内容。不相同，选择会多些。

递归边界。当时，说明已经扫描到了子符串的最后。如下图所示，无论哪一个指针先到达字符串的末尾，则都不再存在任何公共子序列。

上述是基于递归的角度分析问题，完整的代码如下：

当字符串的长度较大时，基于递归的运算量会较大，问题在于递归算法中存在大量的重叠子问题。

2.3 重叠子问题

绘制递归树，可清晰看到重叠子问题的存在。

并且可以看到 和分支包括分支，可以使用缓存方案解决递归中的重叠子问题，让重叠子问题只被计算一次。完整代码如下 ：

递归实现性能不可观，代码层面也稍显繁琐。类似于这样求最值的问题，可以试着使用动态规划来实现。

2.4 动态规划

递归解决问题的思想是由上向下，所谓由上向下，指先搁置规模较大的问题，等规模较小的子问题解决后再回溯出大问题的解。通过上文贴的递归树可以清晰看到求解流程。

动态规划的思想是由下向上，是基于枚举思想。记录每一个子问题的解，最终推导出比之更大问题的解。当然，要求小问题具有独立性和最优性。

无论由上向下，还是由下向上，其本质都是知道子问题答案后，再求解出大问题的答案。动态规划算法是直接了当，递归是迂回求解。

现以求字符串的最长公共子序列为例，讲解动态规划的求解过程。

构建数组，用来记录所有子问题的解，类似于递归实现的缓存器。 于本问题而言，是一个二维数组，理论上讲，从推导出，再从推导出……问题域关心的是最后的推导结论，之前使用过的历史推导结论其实是可以不用存储。有点类似于"忘恩负义"，所以可以对于数组进行压缩。

构建二维数组。先初始化数组的第一行和第一列的值为。推导必须有一个源头，这里的 就是源头。

当 或当或当时可认为最长公共子序列的值为。

如图，让，比较 位置的字符，显然与是不相等的。递归是看后面（还没求解）有多少个子问题可以选择，动态规划是看前面（已经求解）有多个子问题会影响当前子问题。对于当前位置而言，对之有影响的位置有个。如下图标记为黄色区域位置。

位置坐标为。表示中有且中无时最长公共子序列的值。

位置坐标为。表示中无且中无时最长公共子序列的值。

位置坐标为。表示中无且中有时最长公共子序列的值。

可以舍弃位置，然后在位置和位置中求最大值。

不变，改成的值。一路比较和中值，因都不相等，根据前面的分析，很容易填写出值。

移动，重置且移动。

和所在位置的字符不相等时的问题已经分析。

如下图，当 时，的值相等，则影响此位置值的前置位置应该是哪个？

相等，显然最长公共子序列会增加，问题是在哪一个前置子问题的值上加 ？

其实，只需要在如下黄色区域位置的值上加上，此位置表示当中都没有的时候。

按如上分析原理，可以把整个表填写完成。

编码实现：

测试结果：

4. 总结

最长公共子序列很有代表性，分析基于递归和动态规划的实现过程，可以帮助我们理解此类问题，且解决此类问题。