最长公共子序列问题用动态规划解,要输出最长公共子序列,并有改进,python代码
时间: 2024-02-13 18:06:36 浏览: 27
以下是使用动态规划求解最长公共子序列问题并输出最长公共子序列的Python代码:
```python
def lcs(X, Y):
m = len(X)
n = len(Y)
# 创建二维数组来保存子问题的解
L = [[0 for j in range(n+1)] for i in range(m+1)]
# 填充L数组
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])
# 从L[m][n]开始回溯查找最长公共子序列
lcs = ""
i, j = m, n
while i > 0 and j > 0:
if X[i-1] == Y[j-1]:
lcs = X[i-1] + lcs
i -= 1
j -= 1
elif L[i-1][j] > L[i][j-1]:
i -= 1
else:
j -= 1
return lcs
# 示例
X = "ABCBDAB"
Y = "BDCABA"
print(lcs(X, Y)) # 输出 "BCBA"
```
另外,对于最长公共子序列问题,还有一种改进方法是使用滚动数组来减小空间复杂度。滚动数组是指在动态规划中只保存最近一次状态更新所需的数组元素,而不是保存所有状态的数组。这种方法在空间限制较严格的情况下可以提高算法的效率。以下是使用滚动数组的Python代码:
```python
def lcs(X, Y):
m = len(X)
n = len(Y)
# 创建二维数组来保存子问题的解
L = [[0 for j in range(n+1)] for i in range(2)]
# 填充L数组
for i in range(1, m+1):
for j in range(1, n+1):
if X[i-1] == Y[j-1]:
L[i%2][j] = L[(i-1)%2][j-1] + 1
else:
L[i%2][j] = max(L[(i-1)%2][j], L[i%2][j-1])
# 从L[m%2][n]开始回溯查找最长公共子序列
lcs = ""
i, j = m, n
while i > 0 and j > 0:
if X[i-1] == Y[j-1]:
lcs = X[i-1] + lcs
i -= 1
j -= 1
elif L[(i-1)%2][j] > L[i%2][j-1]:
i -= 1
else:
j -= 1
return lcs
# 示例
X = "ABCBDAB"
Y = "BDCABA"
print(lcs(X, Y)) # 输出 "BCBA"
```
这个代码中使用了滚动数组来减小空间复杂度。在L数组中,只保存了最近两次状态的值,因此L数组只有两行。在每次更新L数组时,都使用i%2来表示当前行的索引,使用(i-1)%2来表示前一行的索引。