问题：最长公共子序列

问题描述

最长公共子序列**解决的是**两个**序列的问题，对它进行**递归**就可以将原问题reduce到两个子序列；由于**动态规划算法**是从右至左，自底向上地运用**递归关系，所以它需要首先计算子问题，然后由子问题的解**推导**出更大的问题的解；

step1最长公共子序列的结构（即解的结构）

设序列$X=\{ x_1, x_2, x_3, \dots ,x_m \}$和$Y=\{ x_1, y_2, y_3, \dots ,y_n \}$的最长公共子序列为$Z=\{z_1, z_2, z_3, \dots ,z_k\}$，则

• 若$x_m = y_n$，则$z_k = x_m = y_n$，且 $Z_{k-1}$是$X_{m-1}$和$Y_{n-1}$的最长公共子序列。
• 若$x_m \ne y_n$，且$z_k \ne x_m$，则 $Z$是$X_{m-1}$和$Y$的最长公共子序列。
• 若$x_m \ne y_n$，且$z_k \ne y_n$，则 $Z$是$X$和$Y_{n-1}$的最长公共子序列。

由此可见：两个序列的最长公共子序列蕴含着这两个序列的**前缀**的最长公共子序列，由此**最长公共子序列问题**具有**最优子结构**性质。

step2子问题的递归结构（即建立递归关系）

建立子问题最优值的递归关系：用$c[i][j]$记录序列$X_i$和$Y_j$的最长公共子序列的长度，其中$X_i= \{ x_1, x_2, \dots , x_i \}$；$Y_j = \{ y_1, y_2, \dots , y_j \}$。当$i=0$或$j=0$时，空序列是$X_i$和$Y_j$的**最长公共子序列**，故此时$c[i][j]=0$（递归关系的base case），其他情况下，有最优子结构的性质可建立递归关系如下： $$ c[i][j]= \begin{cases} 0 & i=0, j=0 \ c[i-1][j-1] + 1 & i,j \gt 0 ; x_i = y_j \ \max{ c[i][j-1], c[i-1][j] } i,j \gt 0 ;x_i \ne y_j \end{cases} $$

NOTE:

一、分支、原问题和子问题思想

在 labuladong 经动态规划：编辑距离 中，对此进行了总结:

前文 最长公共子序列 说过，解决两个字符串的动态规划问题，一般都是用两个指针i,j分别指向两个字符串的最后，然后一步步往前走，缩小问题的规模。

step3计算最优值

step4构造最优解

Q&A

Q:计算**子问题的解**，即不同长度的子序列**对**的最长公共子序列，程序中需要将所有的不同长度的子序列的**组合**情况都**枚举**出来，那一共有多少种组合情况呢？这还真是一个比较复杂的问题。

A:上面的想法是错误的，在这个问题中，它并不需要将序列A的所有子序列和序列B的所有子序列进行组合，看了它的**递归关系**与程序的实现，它并没有枚举出两个序列所有的子序列的组合；

从**递归关系**来看，它是从两个序列末端即最后一个元素开始，每次剥离一个字符；

从动态规划的程序实现来看，由于它是从右至左（自底向上）地应用递归关系，所以它是序列的第一个字符开始，每次添加一个字符，直至构建了一个完整的序列；

另外一个非常重要的问题是，如何将保存子问题的解，使用什么样的数据结构？由于子问题的解是不同长度的子序列的组合，一个二维表是可以满足它的需求的，即使用一个**二维表**来将**子问题的解**保存起来，二维表的的第一维是第一个子序列的长度，第二维是第二个子序列的长度，二维表记录的是这种组合下子序列的长度；

上述两个问题都是典型的应用动态规划是否解决实际问题的，我觉得我不能够仅仅局限于它们，而应该将思维打开：

• 递归关系的建立，这是解决问题的根本所在
• 解的表示与记录；上述两个问题都是使用二维表，其实它是由问题而决定的，并不一定是每种动态规划算法都需要使用，我想对于一些更加复杂的问题，可能需要使用三维表等，比如求三个字符串的最长公共子序列；

其实经过上述分析可以看出，动态规划算法到了最后进行实现的时候，实际上是填表；