编辑代码

def lcs(X, Y):
  """
  使用动态规划法求解两个序列的最长公共子序列

  Args:
    X: 序列 X
    Y: 序列 Y

  Returns:
    lcs: 最长公共子序列长度
    path: 最长公共子序列的路径
  """

  m = len(X)
  n = len(Y)
  dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
  path = [[0 for _ in range(n + 1)] for _ in range(m + 1)]

  # 初始化表格
  for i in range(m + 1):
    dp[i][0] = 0
  for j in range(n + 1):
    dp[0][j] = 0

  # 递推关系
  for i in range(1, m + 1):
    for j in range(1, n + 1):
      if X[i - 1] == Y[j - 1]:
        dp[i][j] = dp[i - 1][j - 1] + 1
        path[i][j] = 1  # 标记从左上角转移而来
      else:
        if dp[i - 1][j] > dp[i][j - 1]:
          dp[i][j] = dp[i - 1][j]
          path[i][j] = 2  # 标记从上一行转移而来
        else:
          dp[i][j] = dp[i][j - 1]
          path[i][j] = 3  # 标记从左边一列转移而来

  # 回溯求解最长公共子序列
  i = m
  j = n
  lcs = []
  while i > 0 and j > 0:
    if path[i][j] == 1:
      lcs.append(X[i - 1])
      i -= 1
      j -= 1
    elif path[i][j] == 2:
      i -= 1
    else:
      j -= 1

  # 反转最长公共子序列
  lcs.reverse()

  return dp[m][n], lcs