动态规划-求最长公共子序列LCS长度-输出所有的最长公共子序列LCS-Java实现_递归算法 输出所有的最长公共子序列

题目：
给定两个序列X={x₁,x₂,…,x_m}和Y={y₁,y₂,…,y_n},求X和Y的最长公共子序列。

1 最长公共子序列概念

实现明确一个点就是，子序列是一个序列中去掉若干元素后得到的序列，也就是说子序列的元素下标是递增的就行，不需要在原序列中连续。

最长公共子序列，显而易见就是序列X和Y都有的最长的子序列。

2 BruteForce 暴力求解法

对于序列X的所有长度不超过Y的子序列，都检查是否也是Y的子序列，在检查过程中记录长度做长的。

假设X长度小于Y，X有m个元素，每个元素都有2种选择，在或不在，所以X一共有2^m个不同子序列。此方法需要指数时间。

3 DP 动态规划法

① 最优子结构

首先我们来检查下LCS问题能不能用DP来做。

DP的问题，需要分成的子问题具有最优子结构性质（问题的最优解中包含着每个子问题的最优解），子问题高度重复性，（当然不用把这个理解成必须，只是说这样的问题比较适合用DP来做）。

假设X和Y的最长公共子序列为Z={z₁,z₂,…,z_k},
则把LCS问题，分成下面这样的几个子问题：
(1)若x_m=y_n,则z_k=x_m=y_n,且Z_k-1是X_m-1和Y_n-1的最长公共子序列。
(2)若x_m≠y_n,且z_k≠x_m，则Z_k是X_m-1和Y_n的最长公共子序列。
(2)若x_m≠y_n,且z_k≠y_n，则Z_k是X_m和Y_n-1的最长公共子序列。

现在来证明一下，以上的子问题具有最优子结构性质，用反证法，
(1) 若z_k不等于x_m,因为x_m=y_n,所以把x_m加在z_k后面，{z₁,z₂,…,z_k,x_m}是X和Y的长度为k+1的公共子序列，这与Z是X和Y的最长公共子序列矛盾，因此，必有z_k=x_m=y_n,Z_k-1。
　　若Z_k-1不是X_m-1和Y_n-1的最长公共子序列，则X_m-1和Y_n-1存在长度比k-1大的公共子序列，则将x_m加在其后面，就产生了一个X和Y的长度比k大的公共子序列了，这与这与Z_k是X和Y的最长公共子序列矛盾，
　　综上两点，故z_k=x_m=y_n,且Z_k-1是X_m-1和Y_n-1的最长公共子序列。

(2)若Z_k不是X_m-1和Y_n的最长公共子序列，则Ｘ_m-1和Y_n还存在更长的最长公共子序列W，则W也是X和Y的公共子序列，且W长度>k，这与Z（长度为k）是X和Y的最长公共子序列矛盾。故Z_k是X_m-1和Y_n的最长公共子序列。
(3)若Z_k不是X_m和Y_n-1的最长公共子序列，则Ｘ_m和Y_n-1还存在更长的最长公共子序列W，则W也是X和Y的公共子序列，且W长度>k，这与Z（长度为k）是X和Y的最长公共子序列矛盾。故Z_k是X_m和Y_n-1的最长公共子序列。
综上三点，两个序列最长公共子序列包含了这两个序列的前缀的最长公共子序列，（这句话有点拗口，其实就是X和Y的LCS包含了X_1≤r≤m和Y_1≤s≤n的LCS）因此最长公共子序列具有最优子结构性质。

② 子问题的递归结构
用C[i][j]记录序列X_i和Y_j的LCS长度。

③求最优值，输出LCS
为了构造出LCS，引入一个二维数组b[m][n]，用来记录c[i][j]的值是由哪个子问题得到的。
(1)b[i][j]=1,则表示X_i和Y_j的LCS是从X_i-1和Y_j-1的LCS得到的，在X_i-1和Y_j-1的LCS后加上一个x_i得到。