3. 用动态规划解决最长公共子序列问题。 (15分)suanfasixq

最长公共子序列问题是指给定两个字符串，找到它们之间最长的公共子序列，即两个字符串中都存在的最长的子序列。

动态规划是解决最长公共子序列问题的一种常用方法。具体步骤如下：

1. 定义状态。设 $dp[i][j]$ 表示长度为 $i$ 的字符串 $s1$ 和长度为 $j$ 的字符串 $s2$ 的最长公共子序列长度。

2. 初始化。当其中一个字符串为空时，最长公共子序列长度为0，即 $dp[i][0]=dp[0][j]=0$。

3. 状态转移。当 $s1[i-1]=s2[j-1]$ 时，$dp[i][j]=dp[i-1][j-1]+1$，即最长公共子序列长度加1；当 $s1[i-1]\neq s2[j-1]$ 时，$dp[i][j]=\max(dp[i-1][j],dp[i][j-1])$，即取 $s1$ 的前 $i-1$ 个字符和 $s2$ 的前 $j$ 个字符的最长公共子序列长度，以及取 $s1$ 的前 $i$ 个字符和 $s2$ 的前 $j-1$ 个字符的最长公共子序列长度中的较大值。

4. 最优解。最终结果为 $dp[m][n]$，其中 $m$ 和 $n$ 分别为 $s1$ 和 $s2$ 的长度。

时间复杂度为 $O(mn)$，空间复杂度为 $O(mn)$。

下面是使用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=\texttt{"abcde"}$ 和 $s2=\texttt{"ace"}$，最长公共子序列为 $\texttt{"ace"}$，长度为3。使用上述代码可以得到正确的结果。