最长公共子序列递归算法和动态规划算法

最长公共子序列问题是指：给定两个序列，找出它们最长的公共子序列。最长公共子序列问题是一个经典的计算机科学问题，也是数据比较的基础问题，它常常被用于版本控制（比如Git中的diff）、生物信息学等领域。最长公共子序列问题可以使用递归算法和动态规划算法来解决。

递归算法的思路是：将问题分解为更小的子问题，然后递归地解决这些子问题。具体来说，我们可以定义一个递归函数LCS(X,Y,i,j)，表示求解序列X和序列Y的前i个元素和前j个元素的最长公共子序列。如果X[i] == Y[j]，那么LCS(X,Y,i,j) = LCS(X,Y,i-1,j-1) + 1；否则，LCS(X,Y,i,j) = max(LCS(X,Y,i-1,j), LCS(X,Y,i,j-1))。递归算法的时间复杂度为O(2^n)，其中n为序列的长度。

动态规划算法的思路是：将问题分解为更小的子问题，并且保存子问题的解，避免重复计算。具体来说，我们可以定义一个二维数组dp，其中dp[i][j]表示序列X的前i个元素和序列Y的前j个元素的最长公共子序列的长度。如果X[i] == Y[j]，那么dp[i][j] = dp[i-1][j-1] + 1；否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。动态规划算法的时间复杂度为O(n^2)，其中n为序列的长度。

相关问题

用动态规划算法、递归算法求最长公共子序列

动态规划算法：

动态规划算法的思路是：先构建一个二维数组 dp，其中 dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符的最长公共子序列的长度。然后，依次填充 dp 数组的每个元素，最终得到 dp[m][n] 就是 s1 和 s2 的最长公共子序列的长度。

具体的填充方法是，从左到右、从上到下遍历 dp 数组，根据递归表达式，依次计算出每个 dp[i][j] 的值。最终得到 dp[m][n] 就是所求。

Python代码如下：

def longest_common_subsequence(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

递归算法：

递归算法的思路是：根据递归表达式，依次递归求解 s1 的前 i 个字符和 s2 的前 j 个字符的最长公共子序列的长度。具体的递归过程如下：

1. 如果 s1 或 s2 为空字符串，则它们的最长公共子序列的长度为 0。
2. 如果 s1 和 s2 的最后一个字符相同，则它们的最长公共子序列的长度为它们各去掉最后一个字符后的子串的最长公共子序列的长度加上 1。
3. 如果 s1 和 s2 的最后一个字符不同，则它们的最长公共子序列的长度为它们分别去掉最后一个字符后的子串的最长公共子序列的长度的最大值。

递归函数的代码如下：

def longest_common_subsequence(s1, s2):
    m, n = len(s1), len(s2)
    if m == 0 or n == 0:
        return 0
    if s1[m-1] == s2[n-1]:
        return longest_common_subsequence(s1[:m-1], s2[:n-1]) + 1
    else:
        return max(longest_common_subsequence(s1[:m-1], s2), longest_common_subsequence(s1, s2[:n-1]))

注意：递归算法的时间复杂度较高，不适合处理较长的字符串，而动态规划算法的时间复杂度为 O(mn)，适用于处理长度较大的字符串。

1. 用动态规划算法求最长公共子序列； 用递归算法求最长公共子序列；

1. 使用动态规划算法求解最长公共子序列（Longest Common Subsequence, LCS）问题的步骤如下：

假设有两个序列，分别为序列A和序列B，长度分别为m和n。

- 创建一个二维数组dp，大小为(m+1)×(n+1)，用于记录最长公共子序列的长度。
- 初始化第一行和第一列的值为0。
- 从第二行和第二列开始，依次遍历序列A和序列B的每个元素：
- 如果A[i-1]和B[j-1]相等，则dp[i][j] = dp[i-1][j-1] + 1；
- 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])，即取左边或上边的最大值。
- 最终，dp[m][n]即为最长公共子序列的长度。

可以根据dp数组的记录，反向回溯得到最长公共子序列。

2. 使用递归算法求解最长公共子序列问题的思路如下：

假设有两个序列，分别为序列A和序列B，长度分别为m和n。

- 如果任一序列为空，则最长公共子序列长度为0。
- 如果A[m-1]和B[n-1]相等，则最长公共子序列长度为1加上A[0...m-2]和B[0...n-2]的最长公共子序列长度。
- 否则，最长公共子序列长度为A[0...m-2]和B[0...n-1]的最长公共子序列长度与A[0...m-1]和B[0...n-2]的最长公共子序列长度的较大值。

通过递归的方式，可以依次缩小问题规模，直至问题规模为0，返回结果。但是由于存在重复计算的子问题，递归算法的效率较低，可以通过记忆化搜索或动态规划进行优化。