问题描述

LCS 的定义：

Longest Common Subsequence，最长公共子序列，即两个序列 X 和 Y 的公共子序列中，长度最长的那个，并且公共子序列不同于公共字串，公共子序列可以是不连续的，但是前后位置不变。

LCS 的意义：

求两个序列中最长的公共子序列的算法，广泛的应用在图形相似处理、媒体流的相似比较、计算生物学方面。生物学家常常用该算法进行基因序列比对，由此推测序列的结构、功能和演化过程。
LCS 可以描述两段文字之间的“相似度”，即他们的雷同程度，从而能够用来辨别抄袭。另一方面，对一段文字进行修改之后，计算改动前后文字的最长公共子序列，将除此子序列外的部分提取出来，这种方法半段修改的部分，往往十分准确。简而言之，百度知道、百度百科都用得上。

一、暴力求解：穷举法

1. 假定字符串 X，Y 的长度分别为 m，n；
2. X 的一个子序列下标序列为 {1，2，3，…，m}，因此 X 共有 $2^m$2m 个子序列；同理，Y 有 $2^n$2n 个子序列。
3. 从而穷举法需要指数时间：$O(2^m\cdot 2^n)$O(2m⋅2n)，显然不可取。

二、动态规划法

将大规模的问题转换为小规模的问题：
$LCS(X_m,Y_n)= \begin{cases} \begin{aligned} LCS(X_{m-1},Y_{n-1})+x_m,\quad &当x_m = y_n\\ max\{LCS(X_{m-1},Y_{n}),LCS(X_m,Y_{n-1})\},\quad &当x_m \neq y_n \end{aligned} \end{cases}$LCS(Xm​,Yn​)={LCS(Xm−1​,Yn−1​)+xm​,max{LCS(Xm−1​,Yn​),LCS(Xm​,Yn−1​)},​当xm​=yn​当xm​̸​=yn​​​
其中$X_m，Y_n$Xm​，Yn​分别表示两个取自$X，Y$X，Y的前缀序列，$x_m，y_n$xm​，yn​分别表示$X,Y$X,Y中的第m和n个元素。
$LCS(X_m,Y_n)$LCS(Xm​,Yn​)表示最长公共子序列。

算法思想：

1. 创建二维数组 $C[m,n]$C[m,n]
   $C[i,j]$C[i,j] 记录序列$X_i$Xi​和$Y_j$Yj​的最长公共子序列的长度。
   $c(i, j) = \begin{cases} \begin{aligned} 0, \quad &当i=0或者j=0\\ c(i-1,j-1)+1, \quad &当i>0,j>0,且x_i = y_j\\ max\{c(i-1, j),c(i,j-1)\}, \quad &当i>0,j>0,且x_i\neq y_j \end{aligned} \end{cases}$c(i,j)=⎩⎪⎨⎪⎧​0,c(i−1,j−1)+1,max{c(i−1,j),c(i,j−1)},​当i=0或者j=0当i>0,j>0,且xi​=yj​当i>0,j>0,且xi​̸​=yj​​​
2. 创建二维数据 $B[m,n]$B[m,n]（方向变量），其中，$b[i,j]$b[i,j] 标记 $c[i,j]$c[i,j] 的值是由哪一个子问题的解达到的。即 $c[i,j]$c[i,j] 是由 $c[i-1,j-1]+1$c[i−1,j−1]+1 或者 $c[i-1,j]$c[i−1,j] 或者 $c[i,j-1]$c[i,j−1] 的哪一个得到的。取值范围为 Left，Top，LeftTop 三种情况。

在上述二维数据表中，数值即为 $c[i,j]$c[i,j]，箭头即为方向变量 B 数组中的值{Left，Top，LeftTop}。

具体代码实现：

1. 先求出B数组和C数组：

2. 通过B数组去递归求解最长公共子序列