Python实现最长公共子序列（LCS）算法详解

最长公共子序列（LCS）算法原理

最长公共子序列（Longest Common Subsequence，简称LCS）是动态规划领域的经典基础题目。其核心目标是在两个给定序列中，找出一个最长的子序列，使得该子序列在两个原始序列中都按相同顺序出现（不要求连续）。

假设序列 a 包含 m 个元素，序列 b 包含 n 个元素。算法通过比较序列末尾元素的状态来推导最优解：

1. 元素匹配：若 a[m-1] == b[n-1]，说明当前元素属于公共子序列的一部分，此时子序列长度加 1，比较范围缩小为 a[:m] 和 b[:n]。
2. 元素不匹配：若 a[m-1] != b[n-1]，则无法同时包含这两个元素。此时需要比较两个子问题的最大值：一是 a[:m-1] 与 b[:n] 的最长公共子序列长度，二是 a[:m] 与 b[:n-1] 的最长公共子序列长度。

为了高效计算，我们采用自底向上的方式构建最优值矩阵。整个过程需要两个核心矩阵：

• 长度矩阵（c）：用于存储并计算两个序列在各个子问题下的最长公共子序列长度。
• 状态矩阵（flag）：用于记录推导过程中的决策路径（如来自上方、左方或左上方），以便后续回溯构造具体的最优解序列。

Python 代码实现

以下是完整的 Python 实现代码。代码分为两个主要部分：`lcs` 函数负责计算长度矩阵和状态矩阵，`printLcs` 函数负责根据状态矩阵逆向回溯并输出具体的子序列。

def lcs(a,b): 
  lena=len(a) 
  lenb=len(b) 
  # 初始化长度矩阵和状态矩阵，行列数均比原序列多1，用于处理边界空序列情况
  c=[[0 for i in range(lenb+1)] for j in range(lena+1)] 
  flag=[[0 for i in range(lenb+1)] for j in range(lena+1)] 
  
  # 动态规划填表
  for i in range(lena): 
    for j in range(lenb): 
      if a[i]==b[j]: 
        # 元素匹配：长度加1，标记为'ok'（来自左上方）
        c[i+1][j+1]=c[i][j]+1 
        flag[i+1][j+1]='ok' 
      elif c[i+1][j]>c[i][j+1]: 
        # 元素不匹配：取上方值较大，标记为'left'
        c[i+1][j+1]=c[i+1][j] 
        flag[i+1][j+1]='left' 
      else: 
        # 元素不匹配：取左方值较大，标记为'up'
        c[i+1][j+1]=c[i][j+1] 
        flag[i+1][j+1]='up' 
  return c,flag 

def printLcs(flag,a,i,j): 
  # 递归回溯终止条件
  if i==0 or j==0: 
    return 
  if flag[i][j]=='ok': 
    # 匹配成功：先回溯，再输出当前字符
    printLcs(flag,a,i-1,j-1) 
    print(a[i-1],end='') 
  elif flag[i][j]=='left': 
    # 来自上方：向左回溯
    printLcs(flag,a,i,j-1) 
  else: 
    # 来自左方：向上回溯
    printLcs(flag,a,i-1,j) 
     
# 测试数据
a='ABCBDAB' 
b='BDCABA' 
c,flag=lcs(a,b) 

# 打印长度矩阵
for i in c: 
  print(i) 
print('') 
# 打印状态矩阵
for j in flag: 
  print(j) 
print('') 
# 输出最终的最长公共子序列
printLcs(flag,a,len(a),len(b)) 
print('') 

运行结果分析

运行上述代码后，程序首先输出计算得到的长度矩阵 c 和状态矩阵 flag。通过状态矩阵的回溯，最终输出的最长公共子序列为 BCBA（注：LCS可能不唯一，BCAB也是合法解之一，具体取决于代码中相等时的处理逻辑）。

以上就是Python实现最长公共子序列算法的详细内容，更多关于Python动态规划算法的资料请关注本站其它相关文章！