最长公共子序列 (LCS)

算法

最长公共子序列是指两个序列共同拥有的、保持元素相对顺序的最长子序列。此问题广泛应用于生物信息学、文本相似度分析等领域,是经典的动态规划问题。

时间复杂度:最佳 O(mn) | 平均 O(mn) | 最差 O(mn)
空间复杂度:O(mn)

应用场景/前提条件

  • 动态规划
  • 字符串处理
  • 序列比较

算法讲解

最长公共子序列

介绍

最长公共子序列(Longest Common Subsequence, LCS)是一个经典的动态规划问题,目标是找出两个序列中共同出现的最长子序列的长度。子序列是指从原序列中删除某些元素(也可以不删除)后得到的新序列,但保持剩余元素的相对顺序不变。

问题定义

给定两个序列X = [x₁, x₂, ..., xₘ]和Y = [y₁, y₂, ..., yₙ],找出X和Y的最长公共子序列Z = [z₁, z₂, ..., zₖ],使得Z是X和Y的子序列且长度k最大。

与子串不同,子序列不要求元素连续,只需保持相对顺序。例如,对于序列"ABCBDAB"和"BDCABA",它们的最长公共子序列是"BCBA",长度为4。

算法步骤

  1. 创建一个二维数组dp,其中dp[i][j]表示序列X的前i个元素与序列Y的前j个元素的LCS长度
  2. 初始化边界:dp[i][0] = dp[0][j] = 0(空序列的LCS长度为0)
  3. 自底向上填充dp表:
    • 如果x_i = y_j,则dp[i][j] = dp[i-1][j-1] + 1(匹配成功,LCS长度加1)
    • 如果x_i ≠ y_j,则dp[i][j] = max(dp[i-1][j], dp[i][j-1])(取两种可能的最大值)
  4. 返回dp[m][n]作为最终结果

算法详解

为了更好地理解LCS的动态规划过程,我们以序列X = "ABCBDAB"和Y = "BDCABA"为例,详细分析整个计算流程:

...