《算法分析与设计》作业9----最长公共子序列LCS
目录
1.问题
2.解析
举例如下：
3.设计
3.1算法
3.2实例
明天完善
X=<A,B,C,B,D,A,B> m=7
Y=<B,D,C,A,,B,A> n=6
C初始化
|
i j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
|
|
|
|
|
|
|
2 |
0 |
|
|
|
|
|
|
|
3 |
0 |
|
|
|
|
|
|
|
4 |
0 |
|
|
|
|
|
|
|
5 |
0 |
|
|
|
|
|
|
|
6 |
0 |
|
|
|
|
|
|
|
7 |
0 |
|
|
|
|
|
|
算法1：
（1）i=1 X.A
j=1 ≠B C[1,1]=max(C[1,0],C[0,1])=max(0,0)=0 删除y
j=2 ≠D C[1,2]=max(C[1,1],C[0,2])=max(0,0)=0 删除y
j=3 ≠C C[1,3]=max(C[1,2],C[0,3])=max(0,0)=0 删除y
j=4 =A C[1,4]=C[0,3]+1=1 删除两个
j=5 ≠B C[1,5]=max(C[1,4],C[0,5])=max(1,0)=1 删除y
j=6 =A C[1,6]=C[0,5]+1=1 删除两个
（2）i=2 X.B
j=1 =B C[2,1]=C[1,0]+1=1 删除两个
j=2 ≠D C[2,2]=max(C[2,1],C[1,2])=max(1,0)=1 删除y
j=3 ≠C C[2,3]=max(C[1,2],C[0,3])=max(0,0)=0 删除y
j=4 ≠A C[2,4]=C[0,3]+1=1 删除两个
j=5 =B C[2,5]=max(C[1,4],C[0,5])=max(1,0)=1 删除y
j=6 ≠A C[2,6]=C[0,5]+1=1 删除两个
（3）i=3
（4）i=4
（5）i=5
（6）i=6
（7）i=7
0 0 0 0 0 0 0
0 0 0 0 1 1 1
0 1 1 1 1 2 2
0 1 1 2 2 2 2
0 1 1 2 2 3 3
0 1 2 2 2 3 3
0 1 2 2 3 3 4
0 1 2 2 3 4 4
4.分析
两重循环，故时间复杂度为O(mn)