题目描述

给定序列 X={x1,xn},序列 Z{z1,zn},是 X 的子序列是指存在一个严格递增下标序列{i1,ik}使得对于所有 j=1,..k 有 zj = xij

例如 Z={B,C,D,B}是序列 X={A,B,C,D,B,A}的子序列，想要的递增下标序列为{2,3,5,7}

穷举法

  • 找出 X 字符所有可能的子序列 2^n
  • 对于 x 的每一个子序列，判断其是否是 Y 的一个子序列，需要的时间为 m
  • 求的总时长 (2^n) * m

动态规划

最优值

当 X 有 i 个元素，Y 有 j 个元素，最长公共子序列的长度 lij

1
2
3
4
5
lij = {
  0                       i=0 或者j=0 （边界条件）
  l(i-1,j-1)+1              i>0，j>0,  and Xi = Yj
  max{l[i-1,j],l[i,j-1]}  i>0,j>0,and Xi≠Yj
}

自底向上计算最优值