赞
踩
如果你对其他算法或者案例感兴趣,请考虑阅读我的以下文章。
递归案例-正整数划分.
递归案例-汉诺塔.
递归案例-全排列.
动态规划案例-矩阵连乘.
递归案例-电路布线(含表格填写等超详细,纯人话讲解).
给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},找出X和Y的最长公共子序列。
从字面意思上看:两个序列共同拥有的最长的子序列。还是不理解?没关系,上例子!
我们给两个序列 X4{A,C,B,F} 和 Y5{C,D,B,G,F} ,让我们来求他们的公共子序列。
公共子序列:{C}、{B}、{F}、{C,B}、{B,F}、{C,F}、{C,B,F}。其中的{C,B,F}就是我们要求的最长公共子序列了。
那么有的人就要问了:“学了这个东西有什么用呢?”,其实这个问题在现实中有很多应用:检测两份作业是否抄袭、大学论文查重等等。
我们将两份作业分别看成两个序列,然后求出这两个作业的最长公共子序列,通过判断最长公共子序列的占比就可以大概推测出是否抄袭
作业了。总之,这个问题的价值还是很大滴。
1.首先,这个问题符合最优子结构性质:问题的最优解包含子问题的最优解。举个简单的例子来理解这句话:一个国家里面最厉害的兵,
肯定是他所在的军营里面最厉害的兵;各个军营里面最厉害的兵,经过选拔(武举考试?)就可以有人脱颖而出,成为这个国家最厉害的
兵。
2.其次就是,重叠子问题性质:子问题之间不独立的同时(这是区分分治算法的关键),少量子问题被重复解决了。说白了就是子问题之间有联系的同时有些计算重复了,我们可以在计算第一次的时候将结果记录下来,以后再用到的时候,直接取值,不用再去花时间计算了。
记录下来,以后再用到的时候,直接取值,不用再去花时间计算了。
1. 我们首先规定Xm{x1,x2…,xm}和Yn{y1,y2…,yn}为题目中的两个序列(要注意区分大小写,大写的表示序列,小写表示元素)
2. 我们规定Xi为Xm的前i个元素,Yj为Yn的前j个元素
3. 我们规定C[i,j]为Xi和Yj的最长公共子序列的元素个数。那么我们这道题就变成求C[m,n]的大小同时确定最长公共子序列!
我们有两个序列Xm和Yn以及他俩的最长公共子序列Zk
1. 当xm=yn的时候,Zk-1就是Xm-1和Yn-1的最长公共子序列了。
例如:X3{A,B,C},Y2{B,C},那么他俩的最长公共子序就是列Z2{B,C}了。此时我们的x3=y2,我们就会发现Z2-1{B}就是X3-1{A,B}和
Y2-1{B}的最长公共子序列了。
2. 当xm!=yn(!=表示不等于),xm!=zk的时候,Zk就是Xm-1和Yn的最长子序列了。
例如X4{A,B,C,F},Y3{B,C,D},此时的最长公共子序列就是Z2{B,C}。此时我们的x4!=y3,x4!=z2,我们可以发现Z2{B,C}就是X4-1{A,B,C}
和Y3{B,C,D}的最长公共子序列了。
3. 当yn!=xm,yn!=zk的时候,Zk就是Xm和Yn-1的最长公共子序列了。
例如X3{B,C,D},Y4{A,B,C,F},此时的最长公共子序列就是Z2{B,C}。此时我们的y4!=x3,y4!=z2,我们可以发现Z2{B,C}就是X3{B,C,D}和
Y4-1{A,B,C}的最长公共子序列了。
通过上面的推论,我们把他公式化:
C
[
i
,
j
]
=
{
0
i
=
0
或
者
j
=
0
C
[
i
−
1
,
j
−
1
]
+
1
x
i
=
y
j
m
a
x
(
C
[
i
−
1
,
j
]
,
C
[
i
,
j
−
1
]
)
x
i
!
=
y
j
}
C [i,j]= \begin {Bmatrix} 0&&&&&i=0或者j=0\\ C[i-1,j-1]+1 &&&&& x~i~=y~j~\\ max(C[i-1,j],C[i,j-1])&&&&&x~i~!=y~j~ \end{Bmatrix}
C[i,j]=⎩⎨⎧0C[i−1,j−1]+1max(C[i−1,j],C[i,j−1])i=0或者j=0x i =y j x i !=y j ⎭⎬⎫
1.当xi=yj的时候,就是我们上述推论的第一条(此处的+1指的是上例中的元素C)。
2.当xi!=yj的时候,就是我们上述推论的第二条和第三条。
现有X6{A,C,A,B,D,F}和Y6{B,C,A,D,G,F},求他俩的最长公共子序列。
解:我们采用填表的方式解决,表中填的数据为两个,分别是C[I,j]和↑、←和↖
C[i,j]的值可以通过上述的公式得出,而“箭头”方向的选择则是通过下面的条件进行选择:
1. xi=yj,用↖
2. xi != yj时,如果C[i-1,j]>=C[i,j],用↑,否则用←。
当i=1,j=1时,因为x1!=y1,所以C[1,1]=max(C[i-1,j],C[i,j-1])=0;因为C[i-1,j]>=C[i,j],用↑。
i\ j | \ | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|---|
\ | B | C | A | D | G | F | ||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
1 | A | 0 | ↑0 | |||||
2 | C | 0 | ||||||
3 | A | 0 | ||||||
4 | B | 0 | ||||||
5 | D | 0 | ||||||
6 | F | 0 |
当i=1,j=2时,因为x1!=y2,所以C[1,2]=max(C[i-1,j],C[i,j-1])=0;因为C[i-1,j]>=C[i,j],用↑。
i\ j | \ | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|---|
\ | B | C | A | D | G | F | ||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
1 | A | 0 | ↑0 | ↑0 | ||||
2 | C | 0 | ||||||
3 | A | 0 | ||||||
4 | B | 0 | ||||||
5 | D | 0 | ||||||
6 | F | 0 |
当i=1,j=3时,因为x1=y3,所以C[1,3]= C[i-1,j-1]+1 =1,所以用↖。
i\ j | \ | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|---|
\ | B | C | A | D | G | F | ||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
1 | A | 0 | ↑0 | ↑0 | ↖1 | |||
2 | C | 0 | ||||||
3 | A | 0 | ||||||
4 | B | 0 | ||||||
5 | D | 0 | ||||||
6 | F | 0 |
当i=1,j=4时,因为x1!=y4,所以C[1,4]= max(C[i-1,j],C[i,j-1])=1,因为C[i-1,j]<C[i,j],用←。
i\ j | \ | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|---|
\ | B | C | A | D | G | F | ||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
1 | A | 0 | ↑0 | ↑0 | ↖1 | ←1 | ||
2 | C | 0 | ||||||
3 | A | 0 | ||||||
4 | B | 0 | ||||||
5 | D | 0 | ||||||
6 | F | 0 |
当i=1,j=5时,因为x1!=y5,所以C[1,5]= max(C[i-1,j],C[i,j-1])=1,因为C[i-1,j]<C[i,j],用←。
i\ j | \ | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|---|
\ | B | C | A | D | G | F | ||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
1 | A | 0 | ↑0 | ↑0 | ↖1 | ←1 | ←1 | |
2 | C | 0 | ||||||
3 | A | 0 | ||||||
4 | B | 0 | ||||||
5 | D | 0 | ||||||
6 | F | 0 |
当i=1,j=6时,因为x1!=y6,所以C[1,6]= max(C[i-1,j],C[i,j-1])=1,因为C[i-1,j]<C[i,j],用←。
i\ j | \ | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|---|
\ | B | C | A | D | G | F | ||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
1 | A | 0 | ↑0 | ↑0 | ↖1 | ←1 | ←1 | ←1 |
2 | C | 0 | ||||||
3 | A | 0 | ||||||
4 | B | 0 | ||||||
5 | D | 0 | ||||||
6 | F | 0 |
当i=2,j=1时,因为x2!=y1,所以C[2,1]=max(C[i-1,j],C[i,j-1])=0;因为C[i-1,j]>=C[i,j],用↑。
i\ j | \ | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|---|
\ | B | C | A | D | G | F | ||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
1 | A | 0 | ↑0 | ↑0 | ↖1 | ←1 | ←1 | ←1 |
2 | C | 0 | ↑0 | |||||
3 | A | 0 | ||||||
4 | B | 0 | ||||||
5 | D | 0 | ||||||
6 | F | 0 |
当i=2,j=2时,因为x2=y2,所以C[2,2]= C[i-1,j-1]+1 =1,所以用↖。
i\ j | \ | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|---|
\ | B | C | A | D | G | F | ||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
1 | A | 0 | ↑0 | ↑0 | ↖1 | ←1 | ←1 | ←1 |
2 | C | 0 | ↑0 | ↖1 | ||||
3 | A | 0 | ||||||
4 | B | 0 | ||||||
5 | D | 0 | ||||||
6 | F | 0 |
当i=2,j=3时,因为x2!=y3,所以C[2,3]=max(C[i-1,j],C[i,j-1])=1;因为C[i-1,j]>=C[i,j],用↑。
i\ j | \ | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|---|
\ | B | C | A | D | G | F | ||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
1 | A | 0 | ↑0 | ↑0 | ↖1 | ←1 | ←1 | ←1 |
2 | C | 0 | ↑0 | ↖1 | ↑1 | |||
3 | A | 0 | ||||||
4 | B | 0 | ||||||
5 | D | 0 | ||||||
6 | F | 0 |
当i=2,j=4时,因为x2!=y4,所以C[2,4]=max(C[i-1,j],C[i,j-1])=1;因为C[i-1,j]>=C[i,j],用↑。
i\ j | \ | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|---|
\ | B | C | A | D | G | F | ||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
1 | A | 0 | ↑0 | ↑0 | ↖1 | ←1 | ←1 | ←1 |
2 | C | 0 | ↑0 | ↖1 | ↑1 | ↑1 | ||
3 | A | 0 | ||||||
4 | B | 0 | ||||||
5 | D | 0 | ||||||
6 | F | 0 |
当i=2,j=5时,因为x2!=y5,所以C[2,5]=max(C[i-1,j],C[i,j-1])=1;因为C[i-1,j]>=C[i,j],用↑。
i\ j | \ | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|---|
\ | B | C | A | D | G | F | ||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
1 | A | 0 | ↑0 | ↑0 | ↖1 | ←1 | ←1 | ←1 |
2 | C | 0 | ↑0 | ↖1 | ↑1 | ↑1 | ↑1 | |
3 | A | 0 | ||||||
4 | B | 0 | ||||||
5 | D | 0 | ||||||
6 | F | 0 |
当i=2,j=6时,因为x2!=y6,所以C[2,6]=max(C[i-1,j],C[i,j-1])=1;因为C[i-1,j]>=C[i,j],用↑。
i\ j | \ | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|---|
\ | B | C | A | D | G | F | ||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
1 | A | 0 | ↑0 | ↑0 | ↖1 | ←1 | ←1 | ←1 |
2 | C | 0 | ↑0 | ↖1 | ↑1 | ↑1 | ↑1 | ↑1 |
3 | A | 0 | ||||||
4 | B | 0 | ||||||
5 | D | 0 | ||||||
6 | F | 0 |
已经给大家示范了两行了,后面的由于篇幅原因,我就直接上结果了!
i\ j | \ | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|---|
\ | B | C | A | D | G | F | ||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
1 | A | 0 | ↑0 | ↑0 | ↖1 | ←1 | ←1 | ←1 |
2 | C | 0 | ↑0 | ↖1 | ↑1 | ↑1 | ↑1 | ↑1 |
3 | A | 0 | ↑0 | ↑1 | ↖2 | ←2 | ←2 | ←2 |
4 | B | 0 | ↖1 | ↑1 | ↑2 | ↑2 | ↑2 | ↑2 |
5 | D | 0 | ↑1 | ↑1 | ↑2 | ↖3 | ←3 | ←3 |
6 | F | 0 | ↑1 | ↑1 | ↑2 | ↑3 | ↑3 | ↖4 |
填完表格之后,我们从最后一格根据箭头方向一直往前走。途中↖箭头的记录下来就是最长公共子序列了。
得到的最长公共子序列就是{C,A,D,F}了。
至于为什么↖就是最长公共子序列的元素呢,这个也很好理解,我们从表格上可以看出来的:
看完不一定代表就会了,做一道例题试一试?(答案我会在我做完之后及时给大家发上去的!!!!)
i\ j | \ | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|---|
\ | B | D | C | A | B | A | ||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
1 | A | 0 | ||||||
2 | B | 0 | ||||||
3 | C | 0 | ||||||
4 | B | 0 | ||||||
5 | D | 0 | ||||||
6 | A | 0 | ||||||
6 | B | 0 |
i\ j | \ | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|---|
\ | B | D | C | A | B | A | ||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
1 | A | 0 | ↑0 | ↑0 | ↑0 | ↖1 | ←1 | ↖1 |
2 | B | 0 | ↖1 | ←1 | ←1 | ←1 | ↖2 | ←2 |
3 | C | 0 | ↑1 | ↑1 | ↖2 | ←2 | ↑2 | ↑2 |
4 | B | 0 | ↖1 | ↑1 | ↑2 | ↑2 | ↖3 | ←3 |
5 | D | 0 | ↑1 | ↖2 | ↑2 | ↑2 | ↑3 | ↑3 |
6 | A | 0 | ↑1 | ↑2 | ↑2 | ↖3 | ↑3 | ↖4 |
6 | B | 0 | ↖1 | ↑2 | ↑2 | ↑3 | ↖4 | ↑4 |
所以此题的最长公共子序列为:{B,C,B,A}。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。