通过python用动态规划实现最长公共子序列
时间: 2024-02-28 19:30:26 浏览: 26
最长公共子序列(Longest Common Subsequence, LCS)是指给定两个字符串,找到这两个字符串中都存在的最长的子序列。
动态规划是解决LCS问题的一种常用方法。具体实现是先创建一个二维数组,横轴表示字符串1,纵轴表示字符串2,数组中每个位置存储的值表示当前位置为止两个字符串的公共子序列的长度。然后从左上角开始,一行一行的填充数组,填充的过程中需要根据两个字符串当前位置的字符是否相等来判断数组位置上的值。最后返回数组右下角的值即为LCS的长度。
下面是Python实现的代码示例:
```python
def lcs(str1, str2):
m, n = len(str1), len(str2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if str1[i - 1] == str2[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]
```
这个函数的输入是两个字符串,输出是它们的最长公共子序列的长度。
相关问题
Python动态规划策略实现最长公共子序列。
好的,下面是Python实现最长公共子序列的动态规划策略:
```python
def lcs_length(X, Y):
m = len(X)
n = len(Y)
c = [[0] * (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])
return c[m][n]
# test
X = "ABCDABCE"
Y = "ACEBDF"
print(lcs_length(X, Y)) # output: 4
```
其中,`lcs_length` 函数的参数 `X` 和 `Y` 分别代表两个字符串。`m` 和 `n` 分别代表 `X` 和 `Y` 的长度。`c` 是一个二维数组,用于记录当前子问题的解。`c[i][j]` 表示 `X` 的前 `i` 个字符和 `Y` 的前 `j` 个字符的最长公共子序列长度。
接下来,我们使用两层循环来填充 `c` 数组,具体实现方式如下:
- 如果 `X[i-1]` 和 `Y[j-1]` 相等,则当前字符是公共子序列的一部分,所以 `c[i][j]` 的值应该是 `c[i-1][j-1]` 的基础上加 1。
- 如果 `X[i-1]` 和 `Y[j-1]` 不相等,则当前字符不可能是公共子序列的一部分。此时,我们可以选择忽略 `X` 的最后一个字符,或者忽略 `Y` 的最后一个字符。因此,`c[i][j]` 的值应该是 `c[i-1][j]` 和 `c[i][j-1]` 中的较大值。
最终,我们返回 `c[m][n]`,即 `X` 和 `Y` 的最长公共子序列的长度。
上面的代码中,我们使用了 Python 中的列表推导式来初始化二维数组 `c`。另外,为了方便起见,我们将 `c` 的第一行和第一列都初始化为零。这样,在填充 `c` 数组时,我们就不需要为边界条件单独处理了。
动态规划策略实现最长公共子序列python
最长公共子序列问题是一种经典的动态规划问题,在此为您提供 Python 代码实现:
```python
def lcs(str1, str2):
m = len(str1)
n = len(str2)
# 创建一个 m+1 行,n+1列的二维数组,用于保存子问题的最优解
dp = [[0] * (n+1) for _ in range(m+1)]
# 计算子问题的最优解
for i in range(1, m+1):
for j in range(1, n+1):
if str1[i-1] == str2[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], get_lcs(dp, str1, str2)
def get_lcs(dp, str1, str2):
i, j = len(str1), len(str2)
lcs_str = ''
while i > 0 and j > 0:
if str1[i-1] == str2[j-1]:
lcs_str = str1[i-1] + lcs_str
i -= 1
j -= 1
elif dp[i-1][j] >= dp[i][j-1]:
i -= 1
else:
j -= 1
return lcs_str
```
这个代码中,我们首先创建一个二维数组 dp 来保存子问题的最优解。然后,我们使用两个嵌套的循环遍历 str1 和 str2 中的每个字符,并计算子问题的最优解。最后,我们返回最长公共子序列的长度以及最长公共子序列本身。
在计算子问题的最优解时,我们会根据当前字符是否相等来进行判断。如果相等,那么最长公共子序列的长度应该加上 1,同时我们需要继续考虑 str1 和 str2 中下一个字符的匹配。如果不相等,我们就需要在 str1 和 str2 中分别跳过一个字符,然后继续考虑下一个字符的匹配。
最后,我们使用一个 while 循环来重建最长公共子序列。我们从 dp[m][n] 开始,一步步往回找到最长公共子序列的每个字符,并将它们添加到 lcs_str 中。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)