最长公共子序列问题代码
时间: 2023-12-18 19:54:22 浏览: 30
以下是 Python 代码实现最长公共子序列问题:
```python
def lcs(string1, string2):
"""
动态规划求解最长公共子序列
Args:
string1 (str): 字符串 1
string2 (str): 字符串 2
Returns:
str: 最长公共子序列
"""
m, n = len(string1), len(string2)
# 初始化 dp 数组
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if string1[i - 1] == string2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
# 从 dp 数组中重构最长公共子序列
lcs = ''
i, j = m, n
while i > 0 and j > 0:
if string1[i - 1] == string2[j - 1]:
lcs = string1[i - 1] + lcs
i -= 1
j -= 1
elif dp[i - 1][j] > dp[i][j - 1]:
i -= 1
else:
j -= 1
return lcs
```
使用方法:
```python
>>> string1 = 'ABCDGH'
>>> string2 = 'AEDFHR'
>>> lcs(string1, string2)
'ADH'
```