Python动态规划策略实现最长公共子序列。最长公共子序列问题:对两个类型相同的序列(输入),用动态规划方法计算他们的最长公共子序列,并输出最长公共子序列和最长公共子序列的长度值。
时间: 2023-08-13 08:31:52 浏览: 109
动态规划实现最长公共子序列
好的,这是一个经典的动态规划问题。我们可以使用一个二维数组dp[i][j]表示序列1的前i个字符和序列2的前j个字符的最长公共子序列的长度。具体实现步骤如下:
1. 初始化dp数组,dp[0][j]和dp[i][0]均为0,表示空序列的最长公共子序列长度为0。
2. 遍历序列1和序列2,如果当前字符相等,则dp[i][j] = dp[i-1][j-1]+1;否则,dp[i][j] = max(dp[i-1][j], dp[i][j-1]),即选择序列1前i-1个字符和序列2前j个字符的最长公共子序列长度,或者选择序列1前i个字符和序列2前j-1个字符的最长公共子序列长度。
3. 最后,根据dp数组反向回溯,找到最长公共子序列。
下面是Python代码实现:
```python
def lcs(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])
res = ""
i, j = m, n
while i > 0 and j > 0:
if s1[i-1] == s2[j-1]:
res = s1[i-1] + res
i -= 1
j -= 1
elif dp[i-1][j] > dp[i][j-1]:
i -= 1
else:
j -= 1
return res, dp[m][n]
```
这个函数接受两个字符串作为参数s1和s2,返回它们的最长公共子序列和最长公共子序列的长度值。
阅读全文