最长公共子序列问题:给定两个字符串,求它们的最长公共子序列
时间: 2023-08-02 18:36:54 浏览: 48
最长公共子序列问题可以通过动态规划算法来解决。
定义一个二维数组 dp,其中 dp[i][j] 表示字符串 s1 的前 i 个字符和字符串 s2 的前 j 个字符的最长公共子序列的长度。
状态转移方程如下:
当 s1[i-1] == s2[j-1] 时,说明当前字符可以作为最长公共子序列的一部分,因此 dp[i][j] = dp[i-1][j-1] + 1。
当 s1[i-1] != s2[j-1] 时,说明当前字符不能作为最长公共子序列的一部分,因此需要去掉 s1 的最后一个字符或者去掉 s2 的最后一个字符,取它们的最大值,即 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
最终结果为 dp[m][n],其中 m 和 n 分别为字符串 s1 和 s2 的长度。
以下是 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 = "abcde" 和 s2 = "ace",最长公共子序列为 "ace",长度为 3。