最长公共子序列（Longest Common Subsequence）

最长公共子序列（LCS）是一个在一个序列集合中用来查找所有序列中最长子序列的问题。这与查找最长公共子串的问题不同的地方是：子序列不需要在原序列中占用连续的位置。而最长公共子串（要求连续）和最长公共子序列是不同的。

比如：字符串 ABCBDAB 和字符串 BDCAB 的LCS为 BCAB。

LCS在计算机领域有诸多应用，比如可以：

比较 DNA 序列或蛋白质序列。

比较不同版本的文件，找出更改的部分

文本（代码）相似性检

...

假设有两个版本的文件：

文件 V1: The quick brown fox jumps over the lazy dog.

文件 V2: A quick brown dog jumps over the lazy cat.

通过 LCS 算法，可以找到它们的最长公共子序列为 quick brown jumps over the lazy，剩余的部分为更改，这有助于生成补丁文件和合并冲突。

题目

leetcode 1143 是最长公共子序列的经典问题： > 给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0 。 > >一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 > >- 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的公共子序列是这两个字符串所共同拥有的子序列。 > > 两个字符串的公共子序列是这两个字符串所共同拥有的子序列。

示例 1：

输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace" ，它的长度为 3 。

示例 2：

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。

示例 3：

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。

提示：

1 <= text1.length, text2.length <= 1000
text1 和 text2 仅由小写英文字符组成。

分析

最长公共子序列（Longest Common Subsequence, LCS）问题非常适合使用动态规划来解决，原因在于它具备了动态规划的两个关键特性：最优子结构和重叠子问题。

最优子结构：LCS问题的最优解可以由其子问题的最优解构建而来。具体来说：
- 如果两个序列的最后一个字符相同，那么这个字符必定是LCS的一部分，接下来的问题就转化为了求这两个序列去掉最后一个字符之后的LCS。即 \(LCS(i, j) = LCS(i-1, j-1) + 1\)
- 如果两个序列的最后一个字符不同，则LCS不会同时包含这两个字符，问题转化为求一个序列去掉最后一个字符之后与另一个序列的LCS。即 \(LCS(i, j) = max(LCS(i-1, j), LCS(i, j-1))\)
这种性质允许我们将大问题分解为更小的子问题，通过解决这些子问题来构建原始问题的解。
重叠子问题：在求解 LCS 的过程中，我们会反复遇到相同的子问题。例如，在计算两个序列 \(X\) 和 \(Y\) 的LCS时，可能会多次计算 \(X\) 的前 \(i\) 个字符和 \(Y\) 的前 \(j\) 个字符的LCS。由于这些子问题会被多次求解，我们可以将它们的结果存储起来，避免重复计算，这就是动态规划中所谓的“记忆化”。

求解

动态规划的求解步骤如下：

定义状态
- 在最长公共子序列（LCS）问题中，状态可以用一个二维数组 \(dp\) 表示，其中 \(dp[i][j]\) 表示序列 \(X\) 的前 \(i\) 个字符和序列 \(Y\) 的前 \(j\) 个字符的最长公共子序列的长度。
状态转移方程
- 在上节最优子结构的判断中，已经定义出了状态转移方程：
  - if \(X[i]==Y[j]\)， \(dp[i][j] = dp[i-1][j-1] + 1\)
  - if \(X[i]!=Y[j]\)， \(dp[i][j] = max(dp[i-1][j], dp[i][j-1])\)

python代码实现如下：

class Solution(object):
    def longestCommonSubsequence(self, text1, text2):
        """
        :type text1: str
        :type text2: str
        :rtype: int
        """
        n, m = len(text1), len(text2)
        # 多声明一行一列，方便计算dp[1][1]
        dp = [[0 for j in range(m+1)] for i in range(n+1)]
        for i in range(1, n+1):
            for j in range(1, m+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        return dp[n][m]

最终的\(dp\)表为：

[0, 0, 0, 0]

[0, 1, 1, 1]

[0, 1, 2, 2]

[0, 1, 2, 3]

扩充

如果题目要求我们求出具体的最长公共子序列呢？我们可以根据\(dp\)表进行回溯，思路为

从\(dp[n][m]\)开始向前回溯
如果当前\(X[i]==Y[j]\)，那么说明此时\(X[i]\)（\(Y[j]\)）属于LCS的一部分，则加入LCS；同时\(X\)和\(Y\)都向前推进一位
如果当前\(X[i]!=Y[j]\)，那么我们需要找出LCS是在\(X[i-1]\)和\(Y[j]\)中产生，还是在\(X[i]\)和\(Y[j-1]\)中产生，则只需要对比\(dp[i-1][j]\) 和 \(dp[i][j-1]\)

所以代码如下：

class Solution(object):
    def longestCommonSubsequence(self, text1, text2):
        """
        :type text1: str
        :type text2: str
        :rtype: int
        """
        n, m = len(text1), len(text2)
        # 多声明一行一列，方便计算dp[1][1]
        dp = [[0 for j in range(m+1)] for i in range(n+1)]
        for i in range(1, n+1):
            for j in range(1, m+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        # 回溯
        i, j = n, m
        lcs = []
        while (i > 0 and j > 0):
            if text1[i-1]==text2[j-1]:
                lcs.append(text1[i-1])
                i-=1
                j-=1
            else:
                if dp[i-1][j] > dp[i][j-1]:
                    i-=1
                else:
                    j-=1
        lcs_str = ''.join(lcs)[::-1]

        return dp[n][m], lcs_str

solution = Solution()
lcs_len, lcs = solution.longestCommonSubsequence('abcde', 'ace')
print(lcs_len, lcs)

回溯路径为：

[0, 0, 0, 0]

[0, 1, 1, 1]

[0, 1, 2, 2]

[0, 1, 2, 3]