最长公共子序列问题代码
时间: 2023-07-14 15:13:17 浏览: 54
下面是最长公共子序列问题的 Python 代码:
```python
def lcs(X, Y):
m = len(X)
n = len(Y)
# 创建 DP 表并初始化
dp = [[0] * (n+1) for i in range(m+1)]
# 填充 DP 表
for i in range(1, m+1):
for j in range(1, n+1):
if X[i-1] == Y[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# 返回最长公共子序列的长度和该子序列本身
index = dp[m][n]
lcs = [""] * (index+1)
lcs[index] = ""
i = m
j = n
while i > 0 and j > 0:
if X[i-1] == Y[j-1]:
lcs[index-1] = X[i-1]
i -= 1
j -= 1
index -= 1
elif dp[i-1][j] > dp[i][j-1]:
i -= 1
else:
j -= 1
return dp[m][n], "".join(lcs[:-1])
```
其中,`X` 和 `Y` 分别是两个字符串,函数返回最长公共子序列的长度和该子序列本身。