最长公共子序列动态规划代码
时间: 2023-09-01 16:11:10 浏览: 73
下面是最长公共子序列(LCS)问题的动态规划代码:
```python
def lcs(str1, str2):
m = len(str1)
n = len(str2)
# 创建一个m+1行,n+1列的二维数组,用于存储LCS的长度
lcs = [[0] * (n + 1) for _ in range(m + 1)]
# 递推计算LCS的长度
for i in range(1, m + 1):
for j in range(1, n + 1):
if str1[i - 1] == str2[j - 1]:
lcs[i][j] = lcs[i - 1][j - 1] + 1
else:
lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1])
# 返回LCS的长度
return lcs[m][n]
```
其中,`str1` 和 `str2` 分别是要比较的两个字符串,`m` 和 `n` 分别是两个字符串的长度。`lcs` 是一个二维数组,`lcs[i][j]` 表示 `str1` 的前 `i` 个字符和 `str2` 的前 `j` 个字符的最长公共子序列的长度。
在代码中,我们首先创建一个 `m+1` 行、`n+1` 列的二维数组 `lcs`,用于存储LCS的长度。接下来,我们使用双重循环,递推计算出 `lcs[i][j]` 的值。如果 `str1[i-1]` 和 `str2[j-1]` 相等,那么 `lcs[i][j]` 就等于 `lcs[i-1][j-1] + 1`,否则 `lcs[i][j]` 就等于 `max(lcs[i-1][j], lcs[i][j-1])`。最后,返回 `lcs[m][n]`,即 `str1` 和 `str2` 的最长公共子序列的长度。
阅读全文