求最长公共子系列的长度问题

若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X 的子序列是指存

在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k 有：zj=xij.例如，序列

Z={a,b,f,c}是序列X={a,b,c,f,b,c}的子序列，相应的递增下标序列为{1,2,4,6}。给定2

个序列X 和Y，当另一序列Z 既是X 的子序列又是Y 的子序列时，称Z 是序列X 和Y 的公共

子序列.给定2 个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X 和Y 的最长公共子序

列.

分析：

设系列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ，

则

(1)若xm=yn，则zk=xm=yn，且zk-1 是xm-1 和yn-1 的最长公共子序列.

(2)若xm≠yn 且zk≠xm，则Z 是xm-1 和Y 的最长公共子序列。

(3)若xm≠yn 且zk≠yn，则Z 是X 和yn-1 的最长公共子序列。

由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序

列Xi 和Yj 的最长公共子序列的长度。其中， Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。当

i=0 或j=0 时，空序列是Xi 和Yj 的最长公共子序列。故此时C[i][j]=0。