最长公共子序列问题py
时间: 2024-02-22 08:58:49 浏览: 102
以下是 Python 代码实现:
```python
def longest_common_subsequence(A, B):
m = len(A)
n = 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])
lcs = []
i = m
j = n
while i > 0 and j > 0:
if A[i-1] == B[j-1]:
lcs.append(A[i-1])
i -= 1
j -= 1
elif dp[i-1][j] > dp[i][j-1]:
i -= 1
else:
j -= 1
lcs.reverse()
return dp[m][n], lcs
```
其中,参数 A 和 B 分别为两个序列,函数返回值包括最长公共子序列的长度和最长公共子序列本身。
相关问题
最长公共子序列的py代码
最长公共子序列(Longest Common Subsequence,LCS)是指给定两个序列X和Y,找出一个它们的最长公共子序列。
以下是一个简单的Python代码实现:
```python
def lcs(x, y):
m = len(x)
n = len(y)
# 创建二维数组记录状态转移信息
c = [ * (n + 1) for _ 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]:
c[i][j] = c[i - 1][j - 1] + 1
else:
c[i][j] = max(c[i - 1][j], c[i][j - 1])
# 回溯查找LCS
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 c[i - 1][j] > c[i][j - 1]:
i -= 1
else:
j -= 1
return lcs
```
其中,`x`和`y`分别为两个字符串,`m`和`n`为它们的长度。在函数中,我们创建了一个二维数组`c`来记录状态转移信息,并利用动态规划的思想,从左上角开始逐行逐列地计算每个格子的值。当两个字符相等时,当前位置的值等于左上角位置的值加一;否则,当前位置的值等于左边位置和上边位置中较大的一个。
最后,我们通过回溯查找LCS。具体来说,从右下角开始,如果两个字符相等,则将该字符添加到LCS中,并向左上角移动;否则,如果上方的值大于左侧的值,则向上移动;否则,向左移动。
最长公共子序列问题,设计py动态规划算法
好的!最长公共子序列问题是经典的动态规划问题,可以使用Python来实现。
具体实现步骤如下:
1.定义dp数组,dp[i][j]表示第一个字符串s1的前i个字符与第二个字符串s2的前j个字符的最长公共子序列长度。
2.初始化dp数组,当i=0或j=0时,dp[i][j]均为0。
3.递推求解dp数组,当s1[i-1]等于s2[j-1]时,dp[i][j] = dp[i-1][j-1] + 1;否则,dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
4.返回dp[n][m],其中n和m分别为s1和s2的长度。
下面是实现代码:
```python
def longest_common_subsequence(s1, s2):
m, n = len(s1), len(s2)
dp = [[0] * (n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
```
这样就可以通过函数longest_common_subsequence来求解最长公共子序列问题了。