3、如果只需计算最长公共子序列的长度，而无须构造最优解，则如何改进原有程序可以使 得算法的空间需求大大减少？请改写原程序，使算法的空间复杂度减少为 O(min{m,n})。

可以使用滚动数组来减少空间复杂度，将原来的二维数组改为一维数组。具体地，我们可以定义一个长度为 min(m, n) 的数组 dp，其中 dp[j] 表示字符串 A 的前 i 个字符和字符串 B 的前 j 个字符的最长公共子序列的长度。每次计算 dp[j] 时，只需要使用上一次循环中的 dp[j-1] 和当前循环中的 dp[j]，以及一个临时变量 pre 来更新 dp[j] 即可。具体实现如下所示：

def lcs_length(s1, s2):
    m, n = len(s1), len(s2)
    if m < n:
        s1, s2 = s2, s1
        m, n = n, m
    
    dp = [0] * (n+1)

    for i in range(1, m+1):
        pre = 0
        for j in range(1, n+1):
            temp = dp[j]
            if s1[i-1] == s2[j-1]:
                dp[j] = pre + 1
            else:
                dp[j] = max(dp[j], dp[j-1])
            pre = temp

    return dp[n]

时间复杂度仍然为 O(mn)，但空间复杂度降为 O(min{m,n})。

相关问题

用C++如果只需计算最长公共子序列的长度，而无须构造最优解，则如何改进原有程序可以使 得算法的空间需求大大减少？请改写原程序，使算法的空间复杂度减少为 O(min{m,n})。

原有的最长公共子序列算法是基于动态规划的，用一个二维数组来记录子问题的最优解，空间复杂度为 O(mn)。为了将空间复杂度降为 O(min{m,n})，可以使用滚动数组的技巧，只保留两行二维数组，来存储最优解，具体实现如下：

int lcs_length(char* X, char* Y, int m, int n) {
    int L[2][n+1];
    int i, j, curr = 0, prev = 1;
    for (i = 0; i <= m; i++) {
        curr = i % 2;
        prev = 1 - curr;
        for (j = 0; j <= n; j++) {
            if (i == 0 || j == 0) {
                L[curr][j] = 0;
            } else if (X[i-1] == Y[j-1]) {
                L[curr][j] = L[prev][j-1] + 1;
            } else {
                L[curr][j] = max(L[prev][j], L[curr][j-1]);
            }
        }
    }
    return L[curr][n];
}

在每次循环中，只使用了当前行和上一行的最优解，通过取模运算来切换当前行和上一行的索引，从而实现了空间复杂度的降低。

用自然语言写出最长公共子序列的计算最优值算法。

可以使用动态规划算法来计算最长公共子序列的最优值。具体步骤如下：设字符串A和B长度分别为m和n，令dp[i][j]表示A的前i个字符和B的前j个字符的最长公共子序列长度，则可以得到如下递推式：

1) 当A[i] = B[j]时，dp[i][j] = dp[i-1][j-1] + 1；
2) 当A[i] ≠ B[j]时，dp[i][j] = max(dp[i][j-1], dp[i-1][j])。

其中第一种情况表示当前两个字符相同，将它们加入最长公共子序列中；第二种情况表示当前两个字符不同，需要选择其中一个字符加入最长公共子序列。

最终的最长公共子序列长度即为dp[m][n]。