Python实现子序列系列问题——最长公共子序列

题目描述:给定两个序列X={x1, x2, x3, …xm}和Y={y1, y2, y3, … yn}, 求X和Y的最长公共子序列。

分析:如果采用暴力搜索的方法的话,需要穷举X的所有子序列然后分别和Y的所有子序列进行比较,从而筛选出LCS。X共有2^m个子序列,所以暴力搜索的话复杂度肯定是指数阶的,显然不实用。那我们能否通过X和Y的前缀子序列的结果分析推导出X和Y的子序列呢?

假设X的一个前缀子序列 Xi = {x1, x2, x3, … , xi}, Y的一个前缀子序列Yi = {y1, y2, y3, … , yi}, 并且我们假设已知Xi和Yi的LCS为kij。那么X(i+1)和Y(i+1)的LCS是多少呢?不妨假设其LCS为k(i+1)(j+1)。稍加思考,容易发现有两种情况:(1) 如果X(i+1) = Y(i+1), 那么显然k(i+1)(j+1) = kij + 1      (2)如果X(i+1) != Y(i+1), 那么k(i+1)(j+1) = max(k(i+1)j, ki(j+1))                               看到这里对动态规划有了解的同学通常会发现,这个好像有点符合动态规划的解题特征哎!下面我们就用动态规划的解题思路继续分析一下此题:

步骤一、子问题:要想求Xi和Yj的LCS,我们就必须先求出X(i-1)和Y(j-1)的LCS,X(i)和Y(j-1)的LCS以及X(i-1)和Y(j)的LCS,从而形成了一个递归问题

步骤二、找出动态规划的状态转移公式

假设我们用一个数组c[i,j]来记录Xi和Yj的LCS长度,那么(1) c[i, j] = 0                     若i = 0 或 j = 0                                                                                                                       (2)c[i-1, j-1] + 1                 若i, j>0 且 X[i] = Y[j]                                                                                                               (3)max(c[i-1, j], c[i, j-1])        若i, j>0 且 X[i] != Y[j]

步骤三、根据公式编写代码

(1)由步骤二的公式我们很容易写出递归算法:

[python] view plain copy

  1. #递归求LCS
  2. def LCS_Length(X, Y, i, j):
  3.     if i < 0 or j < 0:#判断递归出口
  4.         return 0
  5.     else:
  6.         if X[i] == Y[j]:
  7.             return (LCS_Length(X, Y, i-1, j-1) + 1)
  8.         return max(LCS_Length(X, Y, i, j-1), LCS_Length(X, Y, i-1, j))

(2)递归转换成自底向上的动态规划算法

[python] view plain copy

  1. #动态规划求LCS
  2. def LCS_Length2(X, Y):
  3.     m = len(X)
  4.     n = len(Y)
  5.     #record列表用于记录Xi和Yj的LCS长度
  6.     record = [[0 for i in range(n)] for j in range(m)]
  7.     #外层循环从i = 0开始,依次计算record[i, j],
  8.     #计算顺序:[0,0],[0,1],[0,2]…., [1,0],[1,1],[1,2]….
  9.     #所以在求解record[i, j]时,我们已经保存了record[i-1, j-1], record[i, j-1], record[i-1,j](解题关键)
  10.     for i in range(m):
  11.         for j in range(n):
  12.             if X[i] == Y[j]:
  13.                 if i>0 and j>0:
  14.                     record[i][j] = record[i-1][j-1] + 1
  15.                 else:
  16.                     record[i][j] = 1
  17.             else:
  18.                 #此处要注意判断边界情况,即i, j 是否等于0
  19.                 if i == 0 and j>0:
  20.                     record[i][j] = record[i][j-1]
  21.                 elif i > 0 and j==0:
  22.                     record[i][j] = record[i-1][j]
  23.                 else:
  24.                     record[i][j] = max(record[i-1][j], record[i][j-1])
  25.     #返回记录LCS的数组                
  26.     return record

步骤四重构问题的解

编写完代码后发现我们好像遗漏了一个问题,那就是:上述代码只帮我们求出了LCS的长度,我们如何重构LCS问题的解呢?也就是怎么输出LCS而不仅是求出LCS的长度。

我们从新分析一下步骤一中的公式,我们是根据X[i]和X[j]是否相等,然后通过record[i-1, j-1],record[i, j-1] 或者record[i-1, j] 推导出record[i, j]的。那现在能否反过来通过比较record[i, j]  和(record[i-1, j-1],record[i, j-1] ,record[i-1, j])的值来确定X[i]和Y[j]的值是否相等呢?答案是肯定的。下面直接上代码:

[python] view plain copy

  1. #打印LCS,因为采用了递归函数所以LCS输出顺序刚好和实际情况一致
  2. def Print_LCS(record, X, i, j):
  3.     #递归出口
  4.     if i==0 or j==0:
  5.         return
  6.     #此时X[i] = Y[j], 所以X[i]在LCS中,输出X[i]
  7.     if record[i][j] == record[i-1][j-1] + 1:
  8.         Print_LCS(record, X, i-1, j-1)
  9.         print(X[i], end = )
  10.     #下面分别讨论X[i] != Y[j]两种情况
  11.     elif record[i][j] == record[i-1][j]:
  12.         Print_LCS(record, X, i-1, j)
  13.     else:
  14.         Print_LCS(record, X, i, j-1)

解题思路:分析问题,将原问题拆分成若干子问题,能通过子问题的解推导出原问题的解,从而发现该问题可以由动态规划解决。接着采用动态规划的解题步骤,找出状态转移公式,通过公式编写代码并且重构原问题的解!

算法优化:此题通过自底向上的动态规划算法解决的话,时间复杂度为O(n^2), 空间复杂度为O(n*n)。但通过分析公式我们可以看出:求解record[i, j]时,只用到了record[i-1]和record[i]这两行,所以我们可以用一个2*n的列表替换原来的n*n的列表。