教程目录

想要实际看看算法是如何工作的吗?

通过交互式可视化深入理解算法运行过程

查看算法可视化

最长公共子序列

介绍

最长公共子序列(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"为例,详细分析整个计算流程:

...

目录