前面两篇我们讲解了01背包问题和最少硬币找零问题。这篇将介绍另一个经典的动态规划问题--最长公共子序列。如果没看过前两篇，可点击下面链接。
问题
给定两个字符串序列 abcadf , acbad，求这两个字符串的最长公共子序列
分析
最长公共子序列问题，有三个点需要注意
- 两个序列长度不一定相同
- 最长子序列是指，在两个字符串序列中以相同顺序出现
- 所求的子序列不需要连续
在进行填表分析之前，根据上面提到的三个点，我们可以很容易地先直接得出答案，最长公共子序列应为 acad
1. 建表
我们给两个子序列前面都加一个空字符，即
input1 = ["","a","c","b","a","d"],input2 = ["","a","b","c","a","d","f"],复制代码
然后构建如下表格
为什么填一堆0呢？表示字符串无法匹配，你可以理解这是一种辅助的计算方式，在分析具体子序列时，不把构建的空字符纳入考虑范围。在后面也会按照前面2篇的思路，使用T[i][j]表示组合的子序列长度。
下面将从左往右，从上往下开始填表。我们在填写某一个表格的时候，只需要考虑小于等于i 和小于等于j的情况。比如我们要填写T[2][2]时，那么此时等同于求字符串 ac,ab的最长公共子序列，填写T[4][5]时，那么此时等同于求 acba，abcad的最长公共子序列长度。
如果你看过前两篇，对于这种填表应该会很熟悉。 下面基于这个表格，开始填表。
2. i =1
我们从第一行开始。
i=1 j=1：此时等同于求字符串 a和a的最长公共子序列长度，很显然结果为1。
i=1 j=2：此时等同于求字符串 a和ab的最长公共子序列长度，结果为1。
i=1 j=3：此时等同于求字符串 a和abc的最长公共子序列长度，结果为1。
只要一个序列只有一个字符，那么另一个序列无论多长，它们的最长公共子序列长度最多只能为1。所以 i=1 行剩余空格都填1。
3. i = 2
i=2 j=1：此时等同于求字符串 ac和a的最长公共子序列长度，结果为1。
i=2 j=2：此时等同于求字符串 ac和ab的最长公共子序列长度，结果为1。
i=2 j=3：此时等同于求字符串 ac和abc的最长公共子序列长度。这时就有意思了。因为根据一开始的分析，求最长公共子序列时，子序列是可以不连续的，因此这两个序列的最长公共子序列应该是 ac，所以这里表格应该填2。
好了，停下，先不用急着继续填，我们需要先分析一下通用思路。
4.填表思路
我们从T[2][3]=2 这一个格分析。很显然去除 c 这个公共字符后，两个字符串还剩下 a, ab。是不是有点熟悉？这个其实就是填写 T[1][2] 时的组合，也就是我们可以假设当 input1[i] == input2[j]时，T[i][j]=T[i-1][j-1]+1。 当input1[i] != input2[j]时，T[i][j]的值，取它上方或左边的较大值，即[i][j] = max(T[i-1][j],T[i][j-1])。
用一句通俗的话来描述这种T[i][j]规律，就是相等左上角加一，不等取上或左最大值，如果上左一样大，优先取左。
好了，不看下面内容，你带着这种规律，把表格剩余内容自己填写完毕。
5.最终表格
理解了这种规律，我们没必要把每一格该怎么填重复叙述了。下面就是最终表格。
我们举个例子，比如 i=5 j=4，此时input1[i] !=input2[j]，我们取它左边（2）或者上方（3）的较大值，所以填写3。
i=5 j=5，此时input1[i] ==input2[j]，我们直接取左上角值加1，左上角的值为T[4][4]=3，所以T[5][5]=4 。
如果还不太理解，可以自己再练习画一次。
6.寻找子串
我们完成填表后，只能求出最长公共子序列的长度，但是无法得知它的具体构成。我们可以参照上一篇硬币问题，从填表的反向角度来寻找子序列。
我们子序列保存在名为 s的数组中，从表格中反向搜索，找到目标字符后，每次都把目标字符插入到数组最前面。
根据前面提供的填表口诀，我们可以反向得出寻找子序列的口诀： 如果T[i][j]来自左上角加一，则是子序列，否则向左或上回退。如果上左一样大，优先取左。
1. 从右下角开始分析，T[5][6]=4，它并不是来自左上角。它左边的值比上方大，所以它来自左边，向左回退，如下图箭头。
2. 接着就定位到 T[5][5]，显然他来自左上角加1，它是子序列。插入数组中，有
s = ['d']复制代码
3. 扣除掉 T[5][5]，可以定位到它的左上角 T[4][4]，如图：
T[4][4]也是来自左上角加1，它也是子序列，把它插入到数组最前面，此时 s 应该是
s = ['a','d']复制代码
4. 按照前面的思路，继续定位分析，最终如下图：
s = ['a','b','a','d']复制代码
伪代码
整个分析过程已经完成了。下面提供代码逻辑，即使不懂 JavaScript，也不会影响你理解，因为没有涉及语言特性。
填表
if(input1[i] == input2[j]){ T[i][j] = T[i-1][j-1] + 1;}else{ T[i][j] = max(T[i-1][j],T[i][j-1])}复制代码 寻找子串
if(input1[i] == input2[j]){ s.insertToIndexZero(input1[i]); //插入到数组最前面 i--; j--;}else{ //向左或向上回退 if(T[i-1][j]>T[i][j-1]){ //向上回退 i--; }else{ //向左回退 j--; }}复制代码 完整代码
最终代码使用 JavaScript 实现，如果你的 Sublime 支持纯 JavaScript，你可以直接复制黏贴代码，command + b 直接运行查看结果，然后修改输入变量，查看更多情况下的输出结果。
//动态规划 -- 最长公共子序列//!!!! T[i][j] 计算，记住口诀：相等左上角加一，不等取上或左最大值function longestSeq(input1,input2,n1,n2){ var T = []; // T[i][j]表示 公共子序列长度 for(let i=0;i 0 && j>0){ if(input1[i] == input2[j]){ result.unshift(input1[i]); i--; j--; }else{ //向左或向上回退 if(T[i-1][j]>T[i][j-1]){ //向上回退 i--; }else{ //向左回退 j--; } } } console.log(result);}//两个序列，长度不一定相等, 从计算表格考虑，把input1和input2首位都补一个用于占位的空字符串var input2 = ["","a","b","c","a","d","f"], input1 = ["","a","c","b","a","d"], n1 = input1.length, n2 = input2.length;console.log(longestSeq(input1,input2,n1,n2));复制代码