最长公共子序列（LCS）问题的空间优化解法
字数 2124 2025-12-05 04:54:34

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

问题描述
最长公共子序列（Longest Common Subsequence, LCS）是动态规划的经典问题：给定两个字符串 text1 和 text2，返回它们的最长公共子序列的长度。子序列不要求连续，但必须保持相对顺序。例如，text1 = "abcde"，text2 = "ace" 的 LCS 是 "ace"，长度为 3。

基础动态规划解法回顾

  1. 定义状态：
    设 dp[i][j] 表示 text1[0..i-1] 和 text2[0..j-1] 的 LCS 长度（索引从 1 开始计数）。
  2. 状态转移方程：
    • 若 text1[i-1] == text2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1；
    • 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
  3. 初始化：
    dp[0][j] = 0 和 dp[i][0] = 0（空字符串与任意字符串的 LCS 长度为 0）。
  4. 时间复杂度：O(mn)，空间复杂度：O(mn)。

空间优化动机

  • 二维 DP 表在字符串较长时（如 m, n ≥ 10^4）可能超出内存限制。
  • 观察发现：计算 dp[i][j] 时仅依赖上一行（dp[i-1][j]）和当前行左侧（dp[i][j-1]），因此只需保留两行。

优化步骤（滚动数组）

  1. 降低维度：
    将二维数组 dp[i][j] 替换为两个一维数组 prev[0..n] 和 curr[0..n]，其中 n = text2.length。

    • prev[j] 存储上一行（i-1）的 DP 值。
    • curr[j] 存储当前行（i）的 DP 值。

  2. 状态转移调整：

    • 遍历 i 从 1 到 m（text1 长度）：
      • 遍历 j 从 1 到 n（text2 长度）：
        • 若 text1[i-1] == text2[j-1]，则 curr[j] = prev[j-1] + 1；
        • 否则，curr[j] = max(prev[j], curr[j-1])。
      • 完成当前行后，将 curr 赋值给 prev，继续下一行。

  3. 关键细节：

    • 初始化 prev 为全 0，表示 i=0 时的基础状态。
    • 每行计算前需设置 curr[0] = 0（对应空子串）。
    • 最终结果存储在 prev[n] 中。

示例演示
以 text1 = "abcde", text2 = "ace" 为例：

  1. 初始化：prev = [0,0,0]（n=3）。
  2. i=1（字符 'a'）：
    • j=1（'a'=='a'）：curr[1] = prev[0] + 1 = 1
    • j=2（'a'!='c'）：curr[2] = max(prev[2]=0, curr[1]=1) = 1
    • j=3（'a'!='e'）：curr[3] = max(prev[3]=0, curr[2]=1) = 1
    • 更新 prev = curr = [0,1,1,1]。
  3. i=2（字符 'b'）：
    • j=1（'b'!='a'）：curr[1] = max(prev[1]=1, curr[0]=0) = 1
    • j=2（'b'!='c'）：curr[2] = max(prev[2]=1, curr[1]=1) = 1
    • j=3（'b'!='e'）：curr[3] = max(prev[3]=1, curr[2]=1) = 1
    • 更新 prev = [0,1,1,1]（结果不变）。
  4. i=3（字符 'c'）：
    • j=2（'c'=='c'）：curr[2] = prev[1] + 1 = 1+1=2
    • j=3（'c'!='e'）：curr[3] = max(prev[3]=1, curr[2]=2) = 2
    • 更新 prev = [0,1,2,2]。
  5. 继续遍历至 i=5，最终 prev[3]=3，即 LCS 长度。

进一步优化（单数组）

  1. 思路：
    仅使用一个数组 dp[0..n]，但需额外变量保存 dp[i-1][j-1]（左上角值）。
  2. 实现：
    • 遍历 i 时，用 diagonal 记录 dp[i-1][0]（初始 0）。
    • 遍历 j 时：
      • 临时保存 dp[j]（即未更新的 dp[i-1][j]）到 temp；
      • 若字符匹配，则 dp[j] = diagonal + 1；
      • 否则，dp[j] = max(dp[j], dp[j-1])（注意此时 dp[j] 仍是上一行值）；
      • 更新 diagonal = temp（为下一列准备左上角值）。
  3. 优势：空间复杂度降至 O(min(m,n))。

总结

  • 核心技巧：利用状态转移的局部性，将二维 DP 压缩为一维。
  • 适用场景：需输出 LCS 长度而非具体序列时（若需构造序列，仍需 O(mn) 空间）。
  • 扩展思考：此优化思想也适用于其他依赖有限历史状态的 DP 问题（如背包问题）。
最长公共子序列（LCS）问题的空间优化解法 问题描述 最长公共子序列（Longest Common Subsequence, LCS）是动态规划的经典问题：给定两个字符串 text1 和 text2 ，返回它们的最长公共子序列的长度。子序列不要求连续，但必须保持相对顺序。例如， text1 = "abcde" ， text2 = "ace" 的 LCS 是 "ace" ，长度为 3。 基础动态规划解法回顾 定义状态 ： 设 dp[i][j] 表示 text1[0..i-1] 和 text2[0..j-1] 的 LCS 长度（索引从 1 开始计数）。 状态转移方程 ： 若 text1[i-1] == text2[j-1] ，则 dp[i][j] = dp[i-1][j-1] + 1 ； 否则， dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 。 初始化 ： dp[0][j] = 0 和 dp[i][0] = 0 （空字符串与任意字符串的 LCS 长度为 0）。 时间复杂度 ：O(mn)， 空间复杂度 ：O(mn)。 空间优化动机 二维 DP 表在字符串较长时（如 m, n ≥ 10^4）可能超出内存限制。 观察发现：计算 dp[i][j] 时仅依赖上一行（ dp[i-1][j] ）和当前行左侧（ dp[i][j-1] ），因此只需保留两行。 优化步骤（滚动数组） 降低维度 ： 将二维数组 dp[i][j] 替换为两个一维数组 prev[0..n] 和 curr[0..n] ，其中 n = text2.length 。 prev[j] 存储上一行（i-1）的 DP 值。 curr[j] 存储当前行（i）的 DP 值。 状态转移调整 ： 遍历 i 从 1 到 m（text1 长度）： 遍历 j 从 1 到 n（text2 长度）： 若 text1[i-1] == text2[j-1] ，则 curr[j] = prev[j-1] + 1 ； 否则， curr[j] = max(prev[j], curr[j-1]) 。 完成当前行后，将 curr 赋值给 prev ，继续下一行。 关键细节 ： 初始化 prev 为全 0，表示 i=0 时的基础状态。 每行计算前需设置 curr[0] = 0 （对应空子串）。 最终结果存储在 prev[n] 中。 示例演示 以 text1 = "abcde" , text2 = "ace" 为例： 初始化： prev = [0,0,0] （n=3）。 i=1 （字符 'a'）： j=1（'a'=='a'）： curr[1] = prev[0] + 1 = 1 j=2（'a'!='c'）： curr[2] = max(prev[2]=0, curr[1]=1) = 1 j=3（'a'!='e'）： curr[3] = max(prev[3]=0, curr[2]=1) = 1 更新 prev = curr = [0,1,1,1] 。 i=2 （字符 'b'）： j=1（'b'!='a'）： curr[1] = max(prev[1]=1, curr[0]=0) = 1 j=2（'b'!='c'）： curr[2] = max(prev[2]=1, curr[1]=1) = 1 j=3（'b'!='e'）： curr[3] = max(prev[3]=1, curr[2]=1) = 1 更新 prev = [0,1,1,1] （结果不变）。 i=3 （字符 'c'）： j=2（'c'=='c'）： curr[2] = prev[1] + 1 = 1+1=2 j=3（'c'!='e'）： curr[3] = max(prev[3]=1, curr[2]=2) = 2 更新 prev = [0,1,2,2] 。 继续遍历至 i=5，最终 prev[3]=3 ，即 LCS 长度。 进一步优化（单数组） 思路 ： 仅使用一个数组 dp[0..n] ，但需额外变量保存 dp[i-1][j-1] （左上角值）。 实现 ： 遍历 i 时，用 diagonal 记录 dp[i-1][0] （初始 0）。 遍历 j 时： 临时保存 dp[j] （即未更新的 dp[i-1][j] ）到 temp ； 若字符匹配，则 dp[j] = diagonal + 1 ； 否则， dp[j] = max(dp[j], dp[j-1]) （注意此时 dp[j] 仍是上一行值）； 更新 diagonal = temp （为下一列准备左上角值）。 优势 ：空间复杂度降至 O(min(m,n))。 总结 核心技巧 ：利用状态转移的局部性，将二维 DP 压缩为一维。 适用场景 ：需输出 LCS 长度而非具体序列时（若需构造序列，仍需 O(mn) 空间）。 扩展思考 ：此优化思想也适用于其他依赖有限历史状态的 DP 问题（如背包问题）。