最长公共子序列是指两个序列共同拥有的、保持元素相对顺序的最长子序列。此问题广泛应用于生物信息学、文本相似度分析等领域,是经典的动态规划问题。
最长公共子序列(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。
为了更好地理解LCS的动态规划过程,我们以序列X = "ABCBDAB"和Y = "BDCABA"为例,详细分析整个计算流程:
...