如何优化最长公共子序列（LCS）算法的时间与空间复杂度？

针对标准LCS算法O(mn)时间和空间复杂度的问题，以下是具体的优化思路与实现：

一、空间复杂度优化（从O(mn)降至O(min(m,n))） #

优化思路 #

观察DP递推公式：

• 当string1[i] == string2[j]时，dp[i+1][j+1] = dp[i][j] + 1
• 当string1[i] != string2[j]时，dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

可以发现，计算第i+1行的所有值时，仅依赖第i行的旧值和当前行已计算的左侧值。因此我们可以用一维数组替代二维数组，优先选择长度更短的字符串对应的维度，将空间复杂度压缩到O(min(m,n))。

需要注意：当字符匹配时，dp[i][j]是上一行前一列的旧值，会被当前行的更新覆盖，因此需要用一个临时变量保存该值，避免丢失。

空间优化后的Java代码（计算LCS长度） #

import java.util.Scanner;

public class OptimizedLCS {
    public static int getLCSLength(String s1, String s2) {
        // 确保s2是较短的字符串，减少空间占用
        if (s1.length() < s2.length()) {
            return getLCSLength(s2, s1);
        }
        int m = s1.length();
        int n = s2.length();
        int[] dp = new int[n + 1];

        for (int i = 0; i < m; i++) {
            int prev = 0; // 保存dp[i][j]的旧值
            for (int j = 0; j < n; j++) {
                int temp = dp[j + 1];
                if (s1.charAt(i) == s2.charAt(j)) {
                    dp[j + 1] = prev + 1;
                } else {
                    dp[j + 1] = Math.max(dp[j + 1], dp[j]);
                }
                prev = temp;
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {
        Scanner myObj = new Scanner(System.in);
        System.out.println("Enter first string");
        String string1 = myObj.nextLine();
        System.out.println("Enter second string");
        String string2 = myObj.nextLine();

        System.out.println("LCS Length: " + getLCSLength(string1, string2));
        myObj.close();
    }
}

注意：如果需要还原实际的LCS字符串，一维数组无法保存完整的回溯路径。此时要么保留必要的回溯状态（会增加部分空间），要么仅在只需LCS长度的场景使用该优化。

二、时间复杂度优化（从O(mn)降至O((m+n)logn)） #

优化思路 #

当字符串长度较大（如10^4级别）时，O(mn)的时间复杂度会导致超时。此时可以将LCS问题转化为**最长递增子序列（LIS）**问题，利用LIS的O(klogk)算法优化时间：

1. 预处理字符串：对string2中的每个字符，记录其所有出现的索引位置（按从后到前的顺序存储，方便后续二分查找）。
2. 生成索引序列：遍历string1的每个字符，在string2的对应字符索引列表中，找到最靠前且小于当前记录的最大索引的位置，将这些索引收集成一个序列。
3. 计算LIS长度：该序列的LIS长度即为LCS的长度，因为递增的索引保证了字符在string2中的顺序与string1一致，符合LCS的顺序要求。

时间优化后的Java代码（计算LCS长度） #

import java.util.*;

public class LCSTimeOptimized {
    public static int getLCSLength(String s1, String s2) {
        // 预处理string2，记录每个字符的索引列表（倒序存储）
        Map<Character, List<Integer>> charIndices = new HashMap<>();
        for (int i = s2.length() - 1; i >= 0; i--) {
            char c = s2.charAt(i);
            charIndices.computeIfAbsent(c, k -> new ArrayList<>()).add(i);
        }

        // 生成索引序列
        List<Integer> indices = new ArrayList<>();
        for (char c : s1.toCharArray()) {
            if (charIndices.containsKey(c)) {
                indices.addAll(charIndices.get(c));
            }
        }

        // 计算LIS长度
        return lengthOfLIS(indices);
    }

    private static int lengthOfLIS(List<Integer> nums) {
        List<Integer> tails = new ArrayList<>();
        for (int num : nums) {
            int idx = Collections.binarySearch(tails, num);
            if (idx < 0) {
                idx = -idx - 1;
            }
            if (idx == tails.size()) {
                tails.add(num);
            } else {
                tails.set(idx, num);
            }
        }
        return tails.size();
    }

    public static void main(String[] args) {
        Scanner myObj = new Scanner(System.in);
        System.out.println("Enter first string");
        String string1 = myObj.nextLine();
        System.out.println("Enter second string");
        String string2 = myObj.nextLine();

        System.out.println("LCS Length: " + getLCSLength(string1, string2));
        myObj.close();
    }
}

优势：该方案在字符串包含大量重复字符时效率提升明显，时间复杂度为O(m + n + klogk)（k为索引序列的长度，最坏情况仍为O(mn)，但实际场景中通常远小于该值）。

内容的提问来源于stack exchange，提问作者Arunabh