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})。