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，返回结果。但是由于存在重复计算的子问题，递归算法的效率较低，可以通过记忆化搜索或动态规划进行优化。

相关问题

用动态规划算法求最长公共子序列的代码； 用递归算法求最长公共子序列的代码；

以下是使用动态规划算法和递归算法求解最长公共子序列问题的代码示例：

动态规划算法代码示例：

def longest_common_subsequence(str1, str2):
    m, n = len(str1), len(str2)
    dp = [[0] * (n+1) for _ in range(m+1)]

    for i in range(1, m+1):
        for j in range(1, n+1):
            if str1[i-1] == str2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    # 回溯获取最长公共子序列
    lcs = []
    i, j = m, n
    while i > 0 and j > 0:
        if str1[i-1] == str2[j-1]:
            lcs.append(str1[i-1])
            i -= 1
            j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1

    return ''.join(reversed(lcs))

str1 = "ABCBDAB"
str2 = "BDCAB"
print(longest_common_subsequence(str1, str2))

递归算法代码示例：

def longest_common_subsequence(str1, str2, m, n):
    if m == 0 or n == 0:
        return ""
    elif str1[m-1] == str2[n-1]:
        return longest_common_subsequence(str1, str2, m-1, n-1) + str1[m-1]
    else:
        lcs1 = longest_common_subsequence(str1, str2, m-1, n)
        lcs2 = longest_common_subsequence(str1, str2, m, n-1)
        return lcs1 if len(lcs1) > len(lcs2) else lcs2

str1 = "ABCBDAB"
str2 = "BDCAB"
m = len(str1)
n = len(str2)
print(longest_common_subsequence(str1, str2, m, 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)，适用于处理长度较大的字符串。