最长公共子序列问题描述
注意:最长公共子序列不一定是连续序列。
例如:"ASAFAGAHAJAK
“与”AAAAAAA
"的最长公共子序列为:AAAAAA
公共子序列的定义
证明最优子结构性质
分析其递归关系式
分别将第一个序列的元素个数设置为0到m,在每一个第一个序列的元素个数0到m的情况下,用内循环让第二个序列的元素从0到n遍历。
也就是说,先从0开始,求解很小的子问题,然后将这些子问题的解存储起来,当求解更大的问题时,会用到这些子问题的结果。这时,直接访问之前计算过的结果,避免了重复运算,这就是动态规划的巧妙之处,也正是需要证明其最优子结构性质的原因。
计算最优值
运行效果
c数组
表示当前状态下,最长公共子序列的长度。s数组
表示当前状态下,最长公共子序列的长度是由哪种情况(1/2/3)计算出来的。
调试中的一个过程截取:
比如说,求解ABCDEFGHI和BDFI的最长公共子序列。
第一步(填0):
当i=0,j=0,1,2,3,...
时,因为X={},所以最长子序列都是0
第二步(填0):i=1,2,3,...,j=0
时,因为Y={},所以最长子序列是0
(用这样的原理,把第一行和第一列都设置为0)
第三步(进入正常循环):
当i=1,j=1
时,也就是说当X的长度为1,Y的长度为1的条件下,X={A}
,Y={B}
,属于情况三(X Y的最后一个元素不相等)
此时,比较X={},Y={B}
与X={A},Y={}
这两种情况下的公共子序列的值,将二者最大值(本例中为0)记录在数c数组中的c[i][j]
位置。
同时,这种情况属于第三种,记为s[i][j]=3
… 根据第三步类推 …
某一个计算瞬间的详细分析如下
下图为调试过程中,截取的i=2,j=4
时候的情况。当前被填写的数组元素:c[2][4]
此时,X={A,B},Y={B,D,F,I}
比较X与Y的最后一个元素,分别为B,I。发现其属于情况三(X Y的最后一个元素不相等)
于是,比较X去掉最后一个元素的最长公共子序列和Y去掉最后一个元素的最长公共子序列,比较过程如下:
X去掉最后一个元素后,X={A},Y={B,D,F,I},查c数组得:其最长公共子序列为c[i-1][j]=0
Y去掉最后一个元素后,X={A,B},Y={B,D,F},查c数组得:其最长公共子序列为c[i][j-1]=1
比较结果为:取最大(后者)。c[i][j] = c[i][j - 1] = 1
,即另c[2][4] = c[2][3] = 1
同时,因为是情况三,所以另s[2][4] = 3
。
从下图可以看到,c[2][4] = 1
已经被填入生效。刚才的分析与实际运行结果相匹配。
…其余中间过程省略
完整填写c数组和s数组之后,最终执行结果↓
补充:填表的顺序图示
输出:BDFI
输出的过程
输出序列字母的过程是一个递归的过程。
见下图,根据s数组判断下一个箭头的指向。可以把s数组的3种情况分别对应到三个指向的箭头,放在数组表格中。然后从右下角的元素开始,一步一步沿着箭头向前走。
或者单步跟踪一下代码比较容易理解。
详细输出过程图示:
代码
注意:需要在宏定义中手动输入序列X,Y的长度,在main函数中输入序列X,Y的具体序列
#include<iostream>#include<cstring>#define XLEN 12#define YLEN 7using namespace std;int c[XLEN + 1][YLEN + 1];//Xi Yj的最长公共子序列的长度 多出1行用来存放长度为0的情况int s[XLEN + 1][YLEN + 1];//c[i][j]的值是由哪一个子问题的解得到的void lcsLength(string x, string y){for (int i = 0; i <= XLEN; i++) c[i][0] = 0;for (int i = 0; i <= YLEN; i++) c[0][i] = 0;for (int i = 1; i <= XLEN; i++)//xi的长度{for (int j = 1; j <= YLEN; j++)//yj的长度{if (x[i - 1] == y[j - 1])//x y序列 最后一个元素相等{c[i][j] = c[i - 1][j - 1] + 1;s[i][j] = 1;}else//x y序列 最后一个元素不相等{if (c[i - 1][j] >= c[i][j - 1])//x去掉现有序列最后一个元素更大{c[i][j] = c[i - 1][j];s[i][j] = 2;}else//y去掉现有序列最后一个元素更大{c[i][j] = c[i][j - 1];s[i][j] = 3;}}}}}void lcs(int i, int j, string x){if (i == 0 || j == 0)return;if (s[i][j] == 1) //x[i] == y[j]{lcs(i - 1, j - 1, x);cout << x[i - 1];}else if (s[i][j] == 2)//c[i - 1][j] >= c[i][j - 1]{lcs(i - 1, j, x);}else lcs(i, j - 1, x);//c[i - 1][j] < c[i][j - 1]}int main(){string x = "ASAFAGAHAJAK";string y = "ASAAAAA";lcsLength(x, y);lcs(XLEN, YLEN, x);cout << endl;system("pause");}