最长公共子序列动态规划法 代码
时间: 2023-11-25 14:48:17 浏览: 53
最长公共子序列(Longest Common Subsequence,LCS)是指在所有给定序列中找到最长的子序列(可以不连续),使得这些子序列在所有给定序列中都出现过。动态规划法是解决LCS问题的一种常用方法。
以下是最长公共子序列动态规划法的代码实现:
```
def LCS(X, Y):
m = len(X)
n = len(Y)
# 初始化二维数组
L = [[0 for j in range(n+1)] for i in range(m+1)]
# 填充数组
for i in range(1, m+1):
for j in range(1, n+1):
if X[i-1] == Y[j-1]:
L[i][j] = L[i-1][j-1] + 1
else:
L[i][j] = max(L[i-1][j], L[i][j-1])
# 返回最长公共子序列长度和子序列本身
return L[m][n], getLCS(X, Y, L)
def getLCS(X, Y, L):
i = len(X)
j = len(Y)
LCS = []
while i > 0 and j > 0:
if X[i-1] == Y[j-1]:
LCS.append(X[i-1])
i -= 1
j -= 1
elif L[i-1][j] > L[i][j-1]:
i -= 1
else:
j -= 1
return ''.join(reversed(LCS))
```
其中,X和Y分别为两个序列,L[i][j]表示X的前i个字符和Y的前j个字符的最长公共子序列长度。getLCS函数用于获取最长公共子序列本身。