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

动态规划算法：

动态规划算法的思路是：先构建一个二维数组 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)，适用于处理长度较大的字符串。