动态规划策略实现最长公共子序列python
时间: 2023-09-23 18:07:22 浏览: 96
DP-LeetCode1143. 最长公共子序列(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 中。
阅读全文