最长公共子序列（Longest Common Subsequence, LCS）问题的优化空间解法

字数 2375 2025-12-14 13:51:15

最长公共子序列（Longest Common Subsequence, LCS）问题的优化空间解法

题目/知识点描述
最长公共子序列（LCS）是一个经典的动态规划问题，它求的是两个序列（通常是字符串）的最长公共子序列的长度，其中子序列不一定要求连续，但必须保持原有顺序。传统的动态规划解法需要使用一个二维数组（大小为 (m+1) × (n+1)，其中 m 和 n 是两个序列的长度）来存储中间状态，空间复杂度为 O(m×n)。然而，在实际应用中，当序列很长时，这个二维数组会占用大量内存。优化空间解法旨在将空间复杂度降低到 O(min(m, n))，甚至 O(1)（但需在特定条件下），同时保持时间复杂度 O(m×n)。本讲解将详细阐述如何逐步优化空间复杂度。

解题过程循序渐进讲解
我将分步骤解释从基础动态规划到空间优化的演变，确保你理解每一步的思路。

步骤1：回顾基础动态规划解法
假设有两个序列：X = x₁x₂...x₍m₎ 和 Y = y₁y₂...y₍n₎。定义 dp[i][j] 表示 X 的前 i 个字符和 Y 的前 j 个字符的 LCS 长度。状态转移方程如下：

如果 i = 0 或 j = 0，dp[i][j] = 0（空序列的 LCS 长度为 0）。
如果 X[i-1] = Y[j-1]（注意索引从 0 开始），则 dp[i][j] = dp[i-1][j-1] + 1。
否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

这需要存储整个 (m+1) × (n+1) 的二维表，空间复杂度为 O(m×n)。

步骤2：空间优化思路——滚动数组
观察状态转移方程，你会发现 dp[i][j] 只依赖于上一行（dp[i-1][j] 和 dp[i-1][j-1]）和当前行的左边元素（dp[i][j-1]）。因此，我们不需要存储整个二维表，而只需维护两行：当前行和上一行。具体步骤：

创建两个一维数组：prev（大小为 n+1）表示上一行，curr（大小为 n+1）表示当前行。
遍历 i 从 1 到 m：
- 对于每个 i，遍历 j 从 1 到 n：
  - 如果 X[i-1] = Y[j-1]，则 curr[j] = prev[j-1] + 1。
  - 否则，curr[j] = max(prev[j], curr[j-1])。
- 在计算完当前行后，将 curr 赋值给 prev，为下一行做准备（或直接交换引用以避免复制）。
最终，curr[n] 即为 LCS 长度。

这样，空间复杂度降低为 O(2*(n+1)) ≈ O(n)（假设 n ≤ m，我们可以用较短的序列长度作为数组大小）。如果需要处理较长的序列，可以交换 X 和 Y 来确保 n 较小。

步骤3：进一步优化——单行数组
实际上，我们可以只用一行数组，但需要小心处理状态依赖。定义 dp[j] 表示当前行的 LCS 长度，但我们需要在更新时保存左上角的值（即 dp[i-1][j-1]），因为它会被覆盖。具体步骤：

初始化一个一维数组 dp，大小为 n+1，所有元素为 0。同时，用一个变量 prev_val 来保存左上角的值。
遍历 i 从 1 到 m：
- 初始化 prev_val = 0（对应 dp[0]）。
- 遍历 j 从 1 到 n：
  - 保存当前 dp[j] 的值到临时变量 temp（这是下一次迭代的左上角值）。
  - 如果 X[i-1] = Y[j-1]，则 dp[j] = prev_val + 1。
  - 否则，dp[j] = max(dp[j], dp[j-1])。
  - 更新 prev_val = temp（为下一列 j+1 准备左上角值）。
最终，dp[n] 即为 LCS 长度。

这个版本的空间复杂度为 O(n+1) ≈ O(n)，只需一个数组和几个辅助变量，是常见的空间优化解法。

步骤4：边界情况和示例验证
以 X = "ABCD", Y = "ACDF" 为例（m=4, n=4）：

初始：dp = [0, 0, 0, 0, 0]。
i=1 (X[0]='A')：比较 Y 的每个字符，当 j=1 (Y[0]='A') 时匹配，更新 dp[1]=1。最终行：[0, 1, 1, 1, 1]。
i=2 (X[1]='B')：匹配到 j=2 (Y[1]='C') 时依赖之前状态，但无匹配。最终行：[0, 1, 1, 1, 1]。
继续处理直到 i=4，最终 dp[4]=3（对应 LCS "ACD"）。

这个示例展示了单行数组如何正确更新，验证了优化解法的有效性。

步骤5：时间复杂度和适用场景

时间复杂度：仍然是 O(m×n)，因为需要双重循环遍历所有字符对。
空间复杂度：O(min(m, n))，通过使用较短的序列长度作为数组大小。
适用场景：当序列非常长（如上万字符）且内存受限时，这种优化至关重要。注意，此方法只能计算 LCS 长度，如果需要重建 LCS 序列，通常需要额外空间（如二维数组）来存储路径信息，但可通过其他技巧（如 Hirschberg 算法）在 O(min(m, n)) 空间内重建。

总结
通过逐步分析，我们理解了 LCS 问题的空间优化核心在于利用状态转移的局部依赖性，从二维数组简化到两行滚动数组，再到单行数组。这种优化思路在其他动态规划问题中也很常见（如 0-1 背包问题）。建议在面试中先解释基础解法，再逐步推导优化版本，以展现深入的系统性思考。

最长公共子序列（Longest Common Subsequence, LCS）问题的优化空间解法题目/知识点描述最长公共子序列（LCS）是一个经典的动态规划问题，它求的是两个序列（通常是字符串）的最长公共子序列的长度，其中子序列不一定要求连续，但必须保持原有顺序。传统的动态规划解法需要使用一个二维数组（大小为 (m+1) × (n+1) ，其中 m 和 n 是两个序列的长度）来存储中间状态，空间复杂度为 O(m×n)。然而，在实际应用中，当序列很长时，这个二维数组会占用大量内存。优化空间解法旨在将空间复杂度降低到 O(min(m, n))，甚至 O(1)（但需在特定条件下），同时保持时间复杂度 O(m×n)。本讲解将详细阐述如何逐步优化空间复杂度。解题过程循序渐进讲解我将分步骤解释从基础动态规划到空间优化的演变，确保你理解每一步的思路。步骤1：回顾基础动态规划解法假设有两个序列： X = x₁x₂...x₍m₎ 和 Y = y₁y₂...y₍n₎ 。定义 dp[i][j] 表示 X 的前 i 个字符和 Y 的前 j 个字符的 LCS 长度。状态转移方程如下：如果 i = 0 或 j = 0 ， dp[i][j] = 0 （空序列的 LCS 长度为 0）。如果 X[i-1] = Y[j-1] （注意索引从 0 开始），则 dp[i][j] = dp[i-1][j-1] + 1 。否则， dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 。这需要存储整个 (m+1) × (n+1) 的二维表，空间复杂度为 O(m×n)。步骤2：空间优化思路——滚动数组观察状态转移方程，你会发现 dp[i][j] 只依赖于上一行（ dp[i-1][j] 和 dp[i-1][j-1] ）和当前行的左边元素（ dp[i][j-1] ）。因此，我们不需要存储整个二维表，而只需维护两行：当前行和上一行。具体步骤：创建两个一维数组： prev （大小为 n+1 ）表示上一行， curr （大小为 n+1 ）表示当前行。遍历 i 从 1 到 m：对于每个 i ，遍历 j 从 1 到 n：如果 X[i-1] = Y[j-1] ，则 curr[j] = prev[j-1] + 1 。否则， curr[j] = max(prev[j], curr[j-1]) 。在计算完当前行后，将 curr 赋值给 prev ，为下一行做准备（或直接交换引用以避免复制）。最终， curr[n] 即为 LCS 长度。这样，空间复杂度降低为 O(2* (n+1)) ≈ O(n)（假设 n ≤ m，我们可以用较短的序列长度作为数组大小）。如果需要处理较长的序列，可以交换 X 和 Y 来确保 n 较小。步骤3：进一步优化——单行数组实际上，我们可以只用一行数组，但需要小心处理状态依赖。定义 dp[j] 表示当前行的 LCS 长度，但我们需要在更新时保存左上角的值（即 dp[i-1][j-1] ），因为它会被覆盖。具体步骤：初始化一个一维数组 dp ，大小为 n+1 ，所有元素为 0。同时，用一个变量 prev_val 来保存左上角的值。遍历 i 从 1 到 m：初始化 prev_val = 0 （对应 dp[0] ）。遍历 j 从 1 到 n：保存当前 dp[j] 的值到临时变量 temp （这是下一次迭代的左上角值）。如果 X[i-1] = Y[j-1] ，则 dp[j] = prev_val + 1 。否则， dp[j] = max(dp[j], dp[j-1]) 。更新 prev_val = temp （为下一列 j+1 准备左上角值）。最终， dp[n] 即为 LCS 长度。这个版本的空间复杂度为 O(n+1) ≈ O(n)，只需一个数组和几个辅助变量，是常见的空间优化解法。步骤4：边界情况和示例验证以 X = "ABCD" , Y = "ACDF" 为例（m=4, n=4）：初始： dp = [0, 0, 0, 0, 0] 。 i=1 (X[ 0]='A')：比较 Y 的每个字符，当 j=1 (Y[ 0]='A') 时匹配，更新 dp[1]=1 。最终行： [0, 1, 1, 1, 1] 。 i=2 (X[ 1]='B')：匹配到 j=2 (Y[ 1]='C') 时依赖之前状态，但无匹配。最终行： [0, 1, 1, 1, 1] 。继续处理直到 i=4，最终 dp[4]=3 （对应 LCS "ACD"）。这个示例展示了单行数组如何正确更新，验证了优化解法的有效性。步骤5：时间复杂度和适用场景时间复杂度：仍然是 O(m×n)，因为需要双重循环遍历所有字符对。空间复杂度：O(min(m, n))，通过使用较短的序列长度作为数组大小。适用场景：当序列非常长（如上万字符）且内存受限时，这种优化至关重要。注意，此方法只能计算 LCS 长度，如果需要重建 LCS 序列，通常需要额外空间（如二维数组）来存储路径信息，但可通过其他技巧（如 Hirschberg 算法）在 O(min(m, n)) 空间内重建。总结通过逐步分析，我们理解了 LCS 问题的空间优化核心在于利用状态转移的局部依赖性，从二维数组简化到两行滚动数组，再到单行数组。这种优化思路在其他动态规划问题中也很常见（如 0-1 背包问题）。建议在面试中先解释基础解法，再逐步推导优化版本，以展现深入的系统性思考。