动态规划：最长公共子序列（LCS）问题

一、问题描述

最长公共子序列（Longest Common Subsequence, LCS）是一个经典的计算机科学问题，也是动态规划算法的代表性应用之一。给定两个序列（通常是字符串），找到它们共有的、最长的子序列。这里的“子序列”是指通过删除原序列中的某些元素（也可以不删除）而不改变剩余元素的相对顺序得到的新序列。

关键点区分：

• 子序列（Subsequence）：元素顺序必须保持，但不要求连续。例如，"ace" 是 "abcde" 的子序列。
• 子串（Substring）：元素顺序必须保持，且必须是连续的。例如，"bcd" 是 "abcde" 的子串。

问题形式化：
输入：两个字符串 text1 和 text2，长度分别为 m 和 n。
输出：这两个字符串的最长公共子序列的长度。有时也要求输出这个子序列本身。

示例：
text1 = "abcde"
text2 = "ace"
它们的公共子序列有 "a", "c", "e", "ac", "ae", "ce", "ace"。其中最长的是 "ace"，长度为 3。

二、解题思路：动态规划

动态规划的核心思想是将复杂问题分解为更小的、重叠的子问题，并通过存储子问题的解（记忆化）来避免重复计算，最终构建出原问题的解。

1. 定义状态（DP数组）

我们定义一个二维数组（或称表格）dp，其维度为 (m+1) x (n+1)。

• dp[i][j] 表示：text1 的前 i 个字符（即 text1[0...i-1]）和 text2 的前 j 个字符（即 text2[0...j-1]）的最长公共子序列的长度。
• 这里使用 i 和 j 表示“前...个字符”，而不是下标，是为了方便处理空字符串的情况。dp[0][j] 和 dp[i][0] 都表示一个空字符串与另一个非空字符串的LCS，其长度自然为0。

2. 建立状态转移方程（递推关系）

状态转移方程是动态规划的灵魂，它描述了如何用已知的子问题的解来求解当前问题。我们需要考虑 text1 的第 i 个字符（text1[i-1]）和 text2 的第 j 个字符（text2[j-1]）之间的关系。

情况分为两种：

• 情况一：当前两个字符相等（text1[i-1] == text2[j-1]）
  这是一个积极的信号。这个相等的字符必定是当前考虑的这两个子串的LCS的最后一个字符。因为如果它不是，我们可以把它加到最后，从而得到一个更长的公共子序列，这与“最长”的定义矛盾。
  因此，text1[0...i-1] 和 text2[0...j-1] 的LCS长度，就等于 text1[0...i-2] 和 text2[0...j-2] 的LCS长度再加1。
  公式： dp[i][j] = dp[i-1][j-1] + 1

• 情况二：当前两个字符不相等（text1[i-1] != text2[j-1]）
  此时，这两个字符不可能同时出现在当前的LCS中。那么，LCS可能来自哪里？它可能有两种来源：

  1. 来自 text1[0...i-1] 和 text2[0...j-2] 的LCS（即忽略 text2 的当前字符）。
  2. 来自 text1[0...i-2] 和 text2[0...j-1] 的LCS（即忽略 text1 的当前字符）。
     为了得到“最长”的公共子序列，我们当然应该取这两种可能性中的最大值。
     公式： dp[i][j] = max(dp[i][j-1], dp[i-1][j])

3. 确定初始状态（Base Case）

初始状态是递推的起点，通常是问题规模最小时的情况。

• 当 i = 0 时，text1 是空字符串。空字符串与任何字符串的LCS长度都是0。所以，对于所有 j，dp[0][j] = 0。
• 当 j = 0 时，text2 是空字符串。任何字符串与空字符串的LCS长度也是0。所以，对于所有 i，dp[i][0] = 0。

4. 计算顺序

我们需要填满整个 (m+1) x (n+1) 的 dp 表格。计算顺序必须保证在计算 dp[i][j] 时，它所依赖的子问题 dp[i-1][j-1]、dp[i][j-1] 和 dp[i-1][j] 都已经被计算出来了。
通常，我们使用两个嵌套循环，外层 i 从 0 到 m，内层 j 从 0 到 n。这个顺序可以确保在计算 (i, j) 位置时，其上方 (i-1, j)、左边 (i, j-1) 和左上方 (i-1, j-1) 的值都是已知的。

5. 最终结果

在填完整个表格后，我们想要的结果就存储在表格的右下角，即 dp[m][n]。它代表了 text1 的全部和 text2 的全部的LCS长度。

三、示例演算

让我们用 text1 = "abcde", text2 = "ace" 来手动模拟一下这个过程。

1. 初始化：创建一个 6x4 的表格（因为 m=5, n=3，所以维度是 (5+1)x(3+1)）。第一行和第一列全部初始化为0。

2. 开始填表 (i 和 j 从1开始)：

   • i=1, j=1: 比较 text1[0]='a' 和 text2[0]='a'。相等！dp[1][1] = dp[0][0] + 1 = 0 + 1 = 1。
   • i=1, j=2: 比较 'a' 和 'c'。不等。dp[1][2] = max(dp[1][1], dp[0][2]) = max(1, 0) = 1。
   • i=1, j=3: 比较 'a' 和 'e'。不等。dp[1][3] = max(dp[1][2], dp[0][3]) = max(1, 0) = 1。
   • i=2, j=1: 比较 'b' 和 'a'。不等。dp[2][1] = max(dp[2][0], dp[1][1]) = max(0, 1) = 1。
   • i=2, j=2: 比较 'b' 和 'c'。不等。dp[2][2] = max(dp[2][1], dp[1][2]) = max(1, 1) = 1。
   • i=2, j=3: 比较 'b' 和 'e'。不等。dp[2][3] = max(dp[2][2], dp[1][3]) = max(1, 1) = 1。
   • i=3, j=1: 比较 'c' 和 'a'。不等。dp[3][1] = max(dp[3][0], dp[2][1]) = max(0, 1) = 1。
   • i=3, j=2: 比较 'c' 和 'c'。相等！dp[3][2] = dp[2][1] + 1 = 1 + 1 = 2。
   • i=3, j=3: 比较 'c' 和 'e'。不等。dp[3][3] = max(dp[3][2], dp[2][3]) = max(2, 1) = 2。
   • i=4, j=1: 比较 'd' 和 'a'。不等。dp[4][1] = max(dp[4][0], dp[3][1]) = max(0, 1) = 1。
   • i=4, j=2: 比较 'd' 和 'c'。不等。dp[4][2] = max(dp[4][1], dp[3][2]) = max(1, 2) = 2。
   • i=4, j=3: 比较 'd' 和 'e'。不等。dp[4][3] = max(dp[4][2], dp[3][3]) = max(2, 2) = 2。
   • i=5, j=1: 比较 'e' 和 'a'。不等。dp[5][1] = max(dp[5][0], dp[4][1]) = max(0, 1) = 1。
   • i=5, j=2: 比较 'e' 和 'c'。不等。dp[5][2] = max(dp[5][1], dp[4][2]) = max(1, 2) = 2。
   • i=5, j=3: 比较 'e' 和 'e'。相等！dp[5][3] = dp[4][2] + 1 = 2 + 1 = 3。

3. 最终表格：

4. 结果：dp[5][3] = 3，与我们的预期一致。

四、代码实现（Python）

def longestCommonSubsequence(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    # 创建 (m+1) x (n+1) 的DP表格，初始化为0
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 开始填表
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                # 字符相等，长度加1
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                # 字符不等，取两种子情况的最大值
                dp[i][j] = max(dp[i][j-1], dp[i-1][j])
    
    # 右下角的值即为答案
    return dp[m][n]

# 测试
text1 = "abcde"
text2 = "ace"
print(longestCommonSubsequence(text1, text2))  # 输出：3

五、扩展：如何输出LCS字符串本身？

要输出LCS而不仅仅是长度，我们需要在填表的基础上，通过回溯 dp 表格来重构这个序列。回溯的方向与递推的方向相反。

回溯规则：

1. 从 dp[m][n] 开始。
2. 如果 text1[i-1] == text2[j-1]，说明这个字符是LCS的一部分。将其记录，然后移动到左上角 (i-1, j-1)。
3. 如果 text1[i-1] != text2[j-1]，则比较 dp[i-1][j] 和 dp[i][j-1]，并向值更大的方向移动（这对应了 max 操作）。如果两者相等，任选一个方向即可。
4. 重复步骤2和3，直到 i 或 j 变为0。

代码实现（输出LCS字符串）：

def getLCSString(text1, text2, dp):
    i, j = len(text1), len(text2)
    lcs_chars = []
    
    while i > 0 and j > 0:
        if text1[i-1] == text2[j-1]:
            # 该字符属于LCS
            lcs_chars.append(text1[i-1])
            i -= 1
            j -= 1  # 移向左上方
        else:
            # 向值更大的方向移动
            if dp[i-1][j] > dp[i][j-1]:
                i -= 1  # 移向上方
            else:
                j -= 1  # 移向左边
    
    # 因为我们是从后往前收集字符的，需要反转一下
    return ''.join(reversed(lcs_chars))

# 在计算完dp表后调用
lcs_length = dp[m][n]
lcs_string = getLCSString(text1, text2, dp)
print(f"LCS长度: {lcs_length}, LCS字符串: {lcs_string}")  # 输出：LCS长度: 3, LCS字符串: ace

六、复杂度分析

• 时间复杂度：O(m * n)。我们需要填充一个 m * n 的表格，每个单元格的计算是常数时间。
• 空间复杂度：O(m * n)。主要开销是DP表格。可以通过“滚动数组”技术优化到 O(min(m, n))，因为计算第 i 行时只依赖于第 i-1 行。

LCS问题是动态规划的基石，深刻理解其状态定义和转移方程的建立过程，对于解决其他动态规划问题大有裨益。