深入理解最长公共子序列（Longest Common Subsequence）问题及其动态规划优化

在计算机科学中，最长公共子序列（Longest Common Subsequence, LCS） 是一个经典的动态规划（Dynamic Programming, DP）问题。它在文本比较、版本控制、基因序列分析、自然语言处理等领域有广泛的应用。本文将详细介绍如何使用动态规划解决LCS问题，并进一步探讨两种优化方法，以减少算法的空间复杂度。此外，我们还将介绍如何回溯得到实际的LCS序列，并讨论相关的应用场景。

问题描述

题目编号：1143. 最长公共子序列

题目内容

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0。

定义：

  • 子序列（Subsequence）：一个字符串的子序列是指这样一个新的字符串，它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是。
  • 公共子序列（Common Subsequence）：两个字符串所共有的子序列。

示例

  • 示例 1：

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

  • 示例 2：

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

  • 示例 3：

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

动态规划思路

1. 定义子问题

动态规划的核心思想是将复杂问题分解为更小的子问题，并存储这些子问题的解以避免重复计算。在LCS问题中，我们可以定义一个二维数组 dp，其中 dp[i][j] 表示字符串 text1 的前 i 个字符和字符串 text2 的前 j 个字符的最长公共子序列的长度。

直观理解：dp[i][j] 表示在 text1 的前 i 个字符和 text2 的前 j 个字符中，能找到的最长公共子序列的长度。

2. 状态转移方程

根据子问题的定义，我们可以推导出以下状态转移方程：

  • 如果当前字符匹配：即 text1.charAt(i-1) == text2.charAt(j-1)，那么 dp[i][j] = dp[i-1][j-1] + 1。
  • 如果当前字符不匹配：那么 dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])。

图示说明：

假设 text1 的第 i 个字符与 text2 的第 j 个字符相同，则LCS长度增加1，并继承于 dp[i-1][j-1]。否则，LCS长度取决于删除 text1 的第 i 个字符或删除 text2 的第 j 个字符后的较大值。

3. 初始化

由于 dp[i][j] 表示的是前 i 个和前 j 个字符的LCS长度，当其中一个字符串为空时，LCS长度为 0。因此，我们需要初始化 dp[0][j] 和 dp[i][0] 为 0。

4. 最终答案

dp[n1][n2] 即为 text1 和 text2 的最长公共子序列的长度，其中 n1 和 n2 分别是 text1 和 text2 的长度。

5. Java实现

下面是标准的动态规划方法的Java实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int n1 = text1.length();
        int n2 = text2.length();
        // 创建二维DP数组
        int[][] dp = new int[n1 + 1][n2 + 1];

        // 填充DP表
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    // 如果字符匹配，从对角线继承并加1
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    // 如果不匹配，取左边和上边的最大值
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[n1][n2];
    }
}

6. 代码解析

  • 二维数组 dp：dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列长度。
  • 遍历顺序：从 i = 1 到 n1，从 j = 1 到 n2，逐步填充 dp 表。
  • 字符匹配：如果 text1.charAt(i-1) == text2.charAt(j-1)，说明当前字符可以作为公共子序列的一部分，此时 dp[i][j] = dp[i-1][j-1] + 1。
  • 字符不匹配：取 dp[i-1][j] 和 dp[i][j-1] 的较大值，表示在当前字符不匹配的情况下，最长公共子序列的长度。

7. 时间和空间复杂度

  • 时间复杂度：O(n1 * n2)，其中 n1 和 n2 分别是 text1 和 text2 的长度。这是因为我们需要遍历所有可能的字符对。
  • 空间复杂度：O(n1 * n2)，需要使用一个二维数组保存所有子问题的结果。

空间优化：滚动数组（Rolling Array）思想

虽然标准的二维动态规划方法直观易懂，但其空间复杂度较高，尤其在处理较长字符串时可能导致内存不足。幸运的是，LCS问题具有状态转移的局部性，即当前状态只依赖于前一行和当前行的状态。因此，我们可以通过优化将空间复杂度从 O(n1 * n2) 降低到 O(min(n1, n2))。

优化方法一：使用两个一维数组

思路

  • 使用两个一维数组 previous 和 current，分别表示前一行和当前行的DP结果。
  • 每遍历一行字符后，将 current 赋值给 previous，为下一行的计算做准备。

实现步骤

  1. 确保 text2 是较短的字符串：通过交换 text1 和 text2，确保 text2 是较短的字符串。这有助于减少空间使用，尤其是在使用单一数组时。
  2. 初始化两个一维数组：previous 和 current，长度为 n2 + 1。
  3. 遍历字符串：逐行更新 current，然后交换 previous 和 current。

优化后的Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        // 确保 text2 是较短的字符串，以优化空间使用
        if (text1.length() < text2.length()) {
            return longestCommonSubsequence(text2, text1);
        }
        
        int n1 = text1.length();
        int n2 = text2.length();
        int[] previous = new int[n2 + 1];
        int[] current = new int[n2 + 1];
        
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    current[j] = previous[j - 1] + 1;
                } else {
                    current[j] = Math.max(current[j - 1], previous[j]);
                }
            }
            // 交换 previous 和 current，准备下一行的计算
            int[] temp = previous;
            previous = current;
            current = temp;
        }
        
        return previous[n2];
    }
}

代码解析

  • 交换数组指针：通过交换 previous 和 current，避免了数组的重新分配和复制。
  • 遍历顺序：与二维数组方法相同，逐行更新 current。
  • 最终结果：存储在 previous[n2] 中，因为在最后一次交换后，previous 存储的是最后一行的结果。

优化方法二：使用单一一维数组

思路

进一步优化空间使用，可以仅使用一个一维数组 dp，并结合一个辅助变量 prev 来保存 dp[i-1][j-1] 的值。通过从前向后遍历 j，确保在更新 dp[j] 时，dp[j-1] 仍然保存着上一行的值。

实现步骤

  1. 确保 text2 是较短的字符串：同样，通过交换 text1 和 text2，确保 text2 是较短的字符串。
  2. 初始化一个一维数组：dp，长度为 n2 + 1。
  3. 使用辅助变量 prev：用于保存 dp[j-1] 在更新前的值，即 dp[i-1][j-1]。
  4. 遍历字符串：从前向后遍历 j，更新 dp[j]。

优化后的Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        // 确保 text2 是较短的字符串，以优化空间使用
        if (text1.length() < text2.length()) {
            return longestCommonSubsequence(text2, text1);
        }
        
        int n1 = text1.length();
        int n2 = text2.length();
        int[] dp = new int[n2 + 1];
        int prev = 0;  // 对应 dp[i-1][j-1]
        
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                int temp = dp[j]; // 保存 dp[j]，即 dp[i-1][j]
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[j] = prev + 1;
                } else {
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                }
                prev = temp; // 更新 prev 为 dp[i-1][j]
            }
            prev = 0; // 重置 prev 为下一行的初始值
        }
        
        return dp[n2];
    }
}

代码解析

  • 变量 prev：用于保存 dp[j-1] 在更新前的值，即 dp[i-1][j-1]。这样在字符匹配时，可以直接使用 prev + 1 来更新 dp[j]。

  • 遍历顺序：从前向后遍历 j，确保在更新 dp[j] 时，dp[j-1] 仍然保存着上一行的值。

  • 更新逻辑

    ：

    • 字符匹配：dp[j] = prev + 1，即 dp[i][j] = dp[i-1][j-1] + 1。
    • 字符不匹配：dp[j] = Math.max(dp[j], dp[j - 1])，即 dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])。

  • 重置 prev：在每行遍历结束后，将 prev 重置为 0，为下一行的计算做准备。

优化思想详解：滚动数组

滚动数组（Rolling Array） 是一种优化动态规划空间复杂度的技术。其核心思想是利用状态转移方程的局部性，只保留必要的状态信息，而不保存整个DP表。

为什么可以使用滚动数组？

在LCS问题中，计算 dp[i][j] 时，只依赖于 上一行（dp[i-1][j] 和 dp[i-1][j-1]）和 当前行的前一个元素（dp[i][j-1]）。这意味着我们不需要保存整个二维表，只需保留当前行和前一行的信息即可。进一步优化后，可以仅使用一个一维数组和一个辅助变量来保存必要的信息。

滚动数组优化的应用

  1. 使用两个一维数组

    ：

    • previous 数组保存前一行的DP结果。
    • current 数组保存当前行的DP结果。
    • 每完成一行的计算后，交换 previous 和 current。

  2. 使用单一一维数组

    ：

    • 通过使用一个一维数组 dp，以及一个辅助变量 prev，保存 dp[i-1][j-1] 的值。
    • 从前向后遍历 j，确保在更新 dp[j] 时，dp[j-1] 仍然保持上一行的值。

示例解析

让我们通过一个具体的示例来理解这两种优化方法的工作原理。

示例：

1
2
text1 = "abc"
text2 = "ac"

预期的 DP 表：

1
2
3
4
5
      ""  a  c
""    0   0  0
a     0   1  1
b     0   1  1
c     0   1  2

使用两个一维数组

  1. 初始化：

    1
    2
    previous = [0, 0, 0]
    current  = [0, 0, 0]

  2. 遍历过程：

    • i = 1 (text1[0] = ‘a’)

      • j = 1 (text2[0] = ‘a’)

        • ‘a’ == ‘a’ → current[1] = previous[0] + 1 = 1

      • j = 2 (text2[1] = ‘c’)

        • ‘a’ != ‘c’ → current[2] = Math.max(current[1], previous[2]) = 1

      • 交换

        1
        2
        previous = [0, 1, 1]
        current  = [0, 0, 0]

    • i = 2 (text1[1] = ‘b’)

      • j = 1 (text2[0] = ‘a’)

        • ‘b’ != ‘a’ → current[1] = Math.max(current[0], previous[1]) = 1

      • j = 2 (text2[1] = ‘c’)

        • ‘b’ != ‘c’ → current[2] = Math.max(current[1], previous[2]) = 1

      • 交换

        1
        2
        previous = [0, 1, 1]
        current  = [0, 0, 0]

    • i = 3 (text1[2] = ‘c’)

      • j = 1 (text2[0] = ‘a’)

        • ‘c’ != ‘a’ → current[1] = Math.max(current[0], previous[1]) = 1

      • j = 2 (text2[1] = ‘c’)

        • ‘c’ == ‘c’ → current[2] = previous[1] + 1 = 2

      • 交换

        1
        2
        previous = [0, 1, 2]
        current  = [0, 0, 0]

  3. 最终结果：

    1
    dp[n2] = previous[2] = 2

使用单一一维数组

  1. 初始化：

    1
    2
    dp = [0, 0, 0]
    prev = 0

  2. 遍历过程：

    • i = 1 (text1[0] = ‘a’)

      • j = 1 (text2[0] = ‘a’)

        • 保存 temp = dp[1] = 0
        • ‘a’ == ‘a’ → dp[1] = prev + 1 = 1
        • 更新 prev = temp = 0

      • j = 2 (text2[1] = ‘c’)

        • 保存 temp = dp[2] = 0
        • ‘a’ != ‘c’ → dp[2] = Math.max(dp[2], dp[1]) = 1
        • 更新 prev = temp = 0

      • 重置

        1
        2
        dp = [0, 1, 1]
        prev = 0

    • i = 2 (text1[1] = ‘b’)

      • j = 1 (text2[0] = ‘a’)

        • 保存 temp = dp[1] = 1
        • ‘b’ != ‘a’ → dp[1] = Math.max(dp[1], dp[0]) = 1
        • 更新 prev = temp = 1

      • j = 2 (text2[1] = ‘c’)

        • 保存 temp = dp[2] = 1
        • ‘b’ != ‘c’ → dp[2] = Math.max(dp[2], dp[1]) = 1
        • 更新 prev = temp = 1

      • 重置

        1
        2
        dp = [0, 1, 1]
        prev = 0

    • i = 3 (text1[2] = ‘c’)

      • j = 1 (text2[0] = ‘a’)

        • 保存 temp = dp[1] = 1
        • ‘c’ != ‘a’ → dp[1] = Math.max(dp[1], dp[0]) = 1
        • 更新 prev = temp = 1

      • j = 2 (text2[1] = ‘c’)

        • 保存 temp = dp[2] = 1
        • ‘c’ == ‘c’ → dp[2] = prev + 1 = 2
        • 更新 prev = temp = 1

      • 重置

        1
        2
        dp = [0, 1, 2]
        prev = 0

  3. 最终结果：

    1
    dp[n2] = dp[2] = 2

为什么称之为滚动数组？

“滚动数组”这一术语来源于这种方法“滚动”地更新数组内容，每次只保留必要的部分，而不是保留整个DP表。它类似于滚动一个窗口，只关注窗口内的数据，忽略窗口外的数据，从而节省空间。

优化方法对比

方法 时间复杂度 空间复杂度 描述
标准二维数组动态规划 O(n1 * n2) O(n1 * n2) 使用二维数组存储所有子问题的解
优化方法一：两个一维数组 O(n1 * n2) O(n2) 使用两个一维数组分别存储当前行和前一行
优化方法二：单一一维数组 O(n1 * n2) O(n2) 使用一个一维数组和一个辅助变量 prev 来存储状态

选择哪种优化方法？

  • 实现复杂度

    ：

    • 两个一维数组的方法实现较为简单，适合大多数情况。
    • 单一一维数组的方法稍微复杂，但在空间受限的情况下更为高效。

  • 空间限制

    ：

    • 对于非常长的字符串，优化后的方法可以显著降低内存消耗，避免内存溢出的问题。

  • 实际应用

    ：

    • 如果只需要LCS的长度，单一一维数组是最佳选择。
    • 如果需要回溯得到LCS序列，使用二维数组更为方便。

根据具体的应用场景和需求，可以选择合适的优化方法。

如何回溯得到实际的LCS序列

除了计算LCS的长度，有时我们还需要得到实际的LCS序列。使用标准的二维DP表，我们可以通过从 dp[n1][n2] 反向回溯，构造出LCS序列。

回溯步骤

  1. 从 dp[n1][n2] 开始。

  2. 比较 text1[i-1] 和 text2[j-1]

    ：

    • 如果相等，则该字符是LCS的一部分，将其加入结果，并移动到 dp[i-1][j-1]。
    • 如果不等，则移动到 dp[i-1][j] 或 dp[i][j-1] 中较大的那个。

  3. 重复上述步骤，直到 i == 0 或 j == 0。

  4. 反转结果字符串，因为回溯过程中是从后往前添加字符的。

Java实现示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public String getLongestCommonSubsequence(String text1, String text2) {
        int n1 = text1.length();
        int n2 = text2.length();
        int[][] dp = new int[n1 + 1][n2 + 1];

        // 填充DP表
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        // 回溯得到LCS序列
        StringBuilder lcs = new StringBuilder();
        int i = n1, j = n2;
        while (i > 0 && j > 0) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                lcs.append(text1.charAt(i - 1));
                i--;
                j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }

        return lcs.reverse().toString();
    }
}

代码解析

  • DP表的构建：与计算LCS长度的方法相同，先构建完整的DP表。

  • 回溯过程

    ：

    • 从 dp[n1][n2] 开始，比较 text1[i-1] 和 text2[j-1]。
    • 如果字符匹配，将其添加到LCS序列中，并同时移动 i 和 j。
    • 如果不匹配，移动到 dp[i-1][j] 或 dp[i][j-1] 中较大的那个方向。

  • 结果反转：因为回溯过程中是从后往前添加字符，最后需要反转得到正确的顺序。

应用场景

LCS问题在多个领域有广泛的应用：

  1. 文本比较和版本控制

    ：

    • 比较不同版本的代码，找出新增、删除或修改的部分。

  2. 基因序列分析

    ：

    • 比较不同物种的DNA序列，分析基因相似性。

  3. 自然语言处理

    ：

    • 句子相似度计算、机器翻译中的对齐问题。

  4. 文件比较工具

    ：

    • 如 diff 工具，用于比较文本文件的不同。

扩展阅读

总结

最长公共子序列（LCS）问题是动态规划的经典应用之一。通过定义合适的子问题、状态转移方程以及优化空间使用的方法，我们可以高效地解决LCS问题。理解和掌握LCS问题不仅有助于解决相关的编程题目，还能在实际应用中发挥重要作用。