目录
1.问题
2.解析
3.设计
4.分析
5.源码
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初始化
算法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 X.C
j=1 ≠B C[3,1]=max(C[3,0],C[2,1])=max(0,1)=1 删除x
j=2 ≠D C[3,2]=max(C[3,1],C[2,2])=max(1,1)=1 删除y
j=3 =C C[3,3]=C[2,2]+1=2 删除两个
j=4 ≠A C[3,4]=max(C[3,3],C[2,4])=max(2,1)=2 删除y
j=5 ≠B C[3,5]=max(C[3,4],C[2,5])=max(2,2)=2 删除y
j=6 ≠A C[3,6]=max(C[3,5],C[2,6])=max(2,2)=2 删除y
(4)i=4 X.B
j=1 =B C[4,1]=C[3,0]+1=1 删除两个
j=2 ≠D C[4,2]=max(C[4,1],C[3,2])=max(1,1)=1 删除y
j=3 ≠C C[4,3]=max(C[4,2],C[3,3])=max(1,2)=2 删除x
j=4 ≠A C[4,4]=max(C[4,3],C[3,4])=max(2,2)=2 删除y
j=5 =B C[4,5]=C[3,4]+1=3 删除两个
j=6 ≠A C[4,6]=max(C[4,5],C[3,6])=max(3,2)=3 删除y
(5)i=5 X.D
j=1 ≠B C[5,1]=max(C[5,0],C[4,1])=max(0,1)=1 删除x
j=2 =D C[5,2]=C[4,1]+1=2 删除两个
j=3 ≠C C[5,3]=max(C[5,2],C[4,3])=max(2,2)=2 删除y
j=4 ≠A C[5,4]=max(C[5,3],C[4,4])=max(2,2)=2 删除y
j=5 ≠B C[5,5]=max(C[5,4],C[4,5])=max(2,3)=3 删除x
j=6 ≠A C[5,6]=max(C[5,5],C[4,6])=max(3,3)=3 删除y
(6)i=6 X.A
j=1 ≠B C[6,1]=max(C[6,0],C[5,1])=max(0,1)=1 删除x
j=2 ≠D C[6,2]=max(C[6,1],C[5,2])=max(1,2)=2 删除x
j=3 ≠C C[6,3]=max(C[6,2],C[5,3])=max(2,2)=2 删除y
j=4 =A C[6,4]=C[5,3]+1=3 删除两个
j=5 ≠B C[6,5]=max(C[6,4],C[5,5])=max(3,3)=3 删除y
j=6 =A C[6,6]=C[5,5]+1=4 删除两个
(7)i=7 X.B
j=1 =B C[7,1]=C[7,0]+1=1 删除两个
j=2 ≠D C[7,2]=max(C[7,1],C[6,2])=max(1,2)=2 删除x
j=3 ≠C C[7,3]=max(C[7,2],C[6,3])=max(2,2)=2 删除y
j=4 ≠A C[7,4]=max(C[7,3],C[6,4])=max(2,3)=3 删除x
j=5 =B C[7,5]=C[6,4]+1=4 删除两个
j=6 ≠A C[7,6]=max(C[7,5],C[6,6])=max(4,4)=4 删除y
得到C[i,j]:B[i,j]表格如下(B[i,j] 1表示删除x;2删除y;3删除两个):
算法2:
string ans用于存储输出的子序列,因为直接输出为逆序,所以借助ans
(1)X=7,Y=6
查表(7,6) 4:2 即删除y
得X=<A,B,C,B,D,A,B>
Y=<B,D,C,A,B>
(2)删除y后X=7,Y=5
查表(7,5) 4:3 即删除两个
得X=<A,B,C,B,D,A>
Y=<B,D,C,A>
ans = B+ ans;
(3)X=6,Y=4
查表(6,4) 3:3 即删除两个
得X=<A,B,C,B,D>
Y=<B,D,C>
ans = A + ans;
(4)X=5,Y=3
查表(5,3) 2:2 即删除y
得X=<A,B,C,B,D>
Y=<B,D>
(5)X=5,Y=2
查表(5,2) 2:3 即删除两个
得X=<A,B,C,B>
Y=<B>
ans = D + ans;
(6)X=4,Y=1
查表(4,1) 1:3 即删除两个
得X=<A,B,C>
Y=<>
ans = B + ans;
算法结束,最终输出ans,即BDAB
4.分析
两重循环,故时间复杂度为O(mn)
5.源码
GitHub地址