问题描述

• 若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。
• 给定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的最长公共子序列。
  由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。
  由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序列的最长公共子序列的长度。其中， Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时C[i][j]=0。其他情况下，由最优子结构性质可建立递归关系如下：
  
  由于在所考虑的子问题空间中，总共有θ(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。 ```cpp Void lcsLength(x,y,b) 1: m←x.length-1; 2: n←y.length-1; 3: c[i][0]=0; c[0][i]=0; 4: for (int i = 1; i <= m; i++) 5: for (int j = 1; j <= n; j++) 6: if (x[i]==y[j]) 7: c[i][j]=c[i-1][j-1]+1; 8: b[i][j]=1; 9: else if (c[i-1][j]>=c[i][j-1]) 10: c[i][j]=c[i-1][j]; 11: b[i][j]=2; 12: else 13: c[i][j]=c[i][j-1]; 14: b[i][j]=3;

构造最长公共子序列 void lcs(int i,int j,char [] x,int [][] b) { if (i ==0 || j==0) return; if (b[i][j]== 1) { lcs(i-1,j-1,x,b); cout<

算法改进：

• 在算法lcsLength和lcs中，可进一步将数组b省去。事实上，数组元素c[i][j]的值仅由c[i-1][j-1]，c[i-1][j]和c[i][j-1]这3个数组元素的值所确定。对于给定的数组元素c[i][j]，可以不借助于数组b而仅借助于c本身在时间内确定c[i][j]的值是由c[i-1][j-1]，c[i-1][j]和c[i][j-1]中哪一个值所确定的。
• 如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，在计算c[i][j]时，只用到数组c的第i行和第i-1行。因此，用2行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至O(min(m,n))。