[动态规划]最长公共子序列
题目：
若给定序列X={x1,x2,…,xm}，则另一序列Y={y1,y2,…,yk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：yj=xij。例如，序列Y={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。
给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。
最长公共子序列（LCS）采用动态规划算法的模板如下：
//最长公共子序列长度
void LCSLength(char x[],char y[],int m,int n){
for(int i = 0;i <= m;i++){ //当y序列为空时 c[i][0]为0
c[i][0] = 0;
}
for(int j = 0;j <= n;j++){ //当x序列为空时 c[0][j]为0
c[0][j] = 0;
}
for(int i = 1;i <= m;i++){
for(int j = 1;j <= n;j++){
if(x[i] == y[j]){ //两个序列当前元素相同 取斜上方的值+1
c[i][j] = c[i-1][j-1] + 1;
}else if(c[i][j-1] >= c[i-1][j]){ //不相同 比较上方和左方值的大小
c[i][j] = c[i][j-1];
}else if(c[i][j-1] < c[i-1][j]){
c[i][j] = c[i-1][j];
}
}
}
}
//最长公共子序列
void LCS(int i, int j){
if(i == 0 || j == 0){
return;
}
if(b[i][j] == 1){ // x[i] == y[j] 斜上方找下一个相同的元素
LCS(i-1,j-1);
cout<<x[i]<<" ";
}else if(b[i][j] == 2){ // c[i][j-1] >= c[i-1][j] 向左找
LCS(i,j-1);
}else if(b[i][j] == 3){ // c[i][j-1] < c[i-1][j] 向右找
LCS(i-1,j);
}
}
状态转移方程为：
- i = 0，j = 0 说明有一个（或两个）序列为空，所以最长公共子序列长度为0；
- x[i] = y[j] 说明此时两个序列当前元素相同，那么找到( x[i-1]，y[j-1] )的最长公共子序列长度即可，所以 c[i][j] = c[i-1][j-1] + 1。
- x[i] != y[j] 说明此时两个序列当前元素不相同，那么找到( x[i-1]，y[j] )或( x[i]，y[j-1] )的最长公共子序列长度即可，取较大值。所以c[i][j] = max(c[i-1][j]，c[i][j-1])。
下面给大家举一个例子，方便理解：
假设 x 序列 的元素为{A，B，C，B，D，A，B}，y 序列的元素为{B，D，C，A，B，A}。我们可以画出对应的二维表，如下图所示。
接下来我们开始动态规划。假设有一个序列为空时，最长公共子序列长度 c[i][j] 的值为0。（没有元素相同，所以最长公共子序列长度为0） 。
接下来双重 for 循环开始遍历剩下的所有点。在坐标（x[1]，y[4]）处，两个序列此时的元素相同，所以取斜上方的值+1。在坐标（x[1]，y[5]）处，两个序列此时的元素不相同，所以比较上方和左方值的大小，取两者中大的。
按照上述方法，可以补全最长公共子序列长度 c[i][j]。
以上求解的是最长公共子序列长度，接下来我们讨论最长公共子序列。 在代码中，我们已经将 c[i][j] 的来源的每一种情况都记录在了 b[i][j] 中。注意，找最长公共子序列应该从b[m][n]开始找，也就是最后一个格子。
- 如果 b[i][j] == 1，表示 x[i] == y[j]，所以向斜上方找上一个相同的元素。
- 如果 b[i][j] == 2，表示当前元素的 c[i][j] 是因为 c[i][j-1] >= c[i-1][j]，所以向左找上一个相同的元素。
- 如果 b[i][j] == 3，表示当前元素的 c[i][j] 是因为 c[i][j-1] < c[i-1][j]，所以向上找上一个相同的元素。
上面的图是根据代码的逻辑画的，但这有一个缺点，它只能找到众多可能中的一个最长公共子序列。
下面是一种可以找到所有可能的最长公共子序列的方法，大家可以参考。
希望大家学有所获！