代码实现求两个序列的最长公共子序列,以及数据测试求出这个子序列
时间: 2024-05-12 13:17:25 浏览: 6
可以使用动态规划算法来求解两个序列的最长公共子序列。首先,定义一个二维数组 dp[i][j] 表示序列 A 的前 i 个字符和序列 B 的前 j 个字符的最长公共子序列长度,其中 A 和 B 分别表示两个序列。
然后,根据状态转移方程 dp[i][j] 的定义,可以得到如下递推式:
如果 A[i-1] == B[j-1],则 dp[i][j] = dp[i-1][j-1] + 1。
如果 A[i-1] != B[j-1],则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
最终,dp[m][n] 即为序列 A 和 B 的最长公共子序列长度,其中 m 和 n 分别表示两个序列的长度。
以下是 Python 代码实现和数据测试:
```
def lcs(A, B):
m, n = len(A), len(B)
dp = [[0] * (n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if A[i-1] == B[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# reconstruct the solution
lcs = []
i, j = m, n
while i > 0 and j > 0:
if A[i-1] == B[j-1]:
lcs.append(A[i-1])
i, j = i-1, j-1
elif dp[i-1][j] > dp[i][j-1]:
i -= 1
else:
j -= 1
return ''.join(reversed(lcs))
# data testing
A = 'ACBDEA'
B = 'ABCDA'
print(lcs(A, B)) # expect 'ABDA'
```