实验六：最长公共子数列（动态规划）报告
2017061111 李静娴
1．问题描述
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定
序列
X={ }
，则另一序列
Z={
1 2
, ,...,
m
z z z
}
是
X
的子序列是指存在一个严格递增
的下标序列
{ }
，使得对于所有
j=1,2,
…
,k
有
=
。例如，序列
Z={B,C,D,B}
是序列
X={A,B,C,B,D,A,B}
的子序列，相应的递增下标序列为
{2,3,5,7}
。给定两个序列
X
和
Y
，当另一
序列
Z
既是
X
的子序列又是
Y
的子序列时，称
Z
是序列
X
和
Y
的公共子序列。例如，若
X={
A,B,C,B,D,A,B}
和
Y={B,D,C,A,B,A}
，则序列
{B,C,A}
是
X
和
Y
的一个公共子序列，序列
{B,C,B,A}
也是
X
和
Y
的一个公共子序列。而且，后者是
X
和
Y
的一个最长公共子序列，因为
X
和
Y
没有长度大于
4
的公共子序列。给定两个序列
X={ }
和
Y={ }
，
要求找出
X
和
Y
的一个最长公共子序列。
2．实验目的
（1）熟悉动态规划算法，并学以致用
（2）熟练掌握最长公共子序列算法
3．实验原理
1.
问题解析：设
X={A,B,C,B,D,A,B},Y={B,D,C,A,B,A}
。求
X
，
Y
的最长公共子序列最容易
想到的方法是穷举法。对
X
的多有子序列，检查它是否也是
Y
的子序列，从而确定它是否
为
X
和
Y
的公共子序列。由集合的性质知，元素为
m
的集合共有
2^m
个不同子序列，因此，
穷举法需要指数级别的运算时间。进一步分解问题特性，最长公共子序列问题实际上具有
最优子结构性质。
设序列
X={ }
和
Y={ }
的最长公共子序列为
Z={
1 2
, ,...,
m
z z z
}
。则有：
(1)
若 ，则 ，且 是 和 的最长公共子序列。
(2)
若 且 ，则
Z
是 和
y
的最长公共子序列。
(3)
若 且 ，则
Z
是
x
和 的最长公共子序列。
其中，
={ }
，
={ }
，
Zk-1={ }
。
2.
递推关系：用
c[i][j]
记录序列
Xi
和
Yj
的最长公共子序列的长度。其中
={ }
，
={ }
。当
i=0
或
j=0
时，空序列是 和 的最长公共子序列。此时，
c[i]
[j]=0
；当
i,j>0
，
=
时，
c[i][j]=c[i-1][j-1]+1
；当
i,j>0
，
!=
时，
c[i][j]=max{c[i][j-1],c[i-1]
[j]}
，由此建立递推关系如下：
评论0