动态规划法求最长公共子序列代码
时间: 2023-11-29 17:06:08 浏览: 40
动态规划法求最长公共子序列的代码如下:
```
def lcs(X, Y):
m = len(X)
n = len(Y)
L = [[None]*(n+1) for i in range(m+1)]
for i in range(m+1):
for j in range(n+1):
if i == 0 or j == 0:
L[i][j] = 0
elif X[i-1] == Y[j-1]:
L[i][j] = L[i-1][j-1] + 1
else:
L[i][j] = max(L[i-1][j], L[i][j-1])
return L[m][n]
```
其中,X和Y分别为两个字符串,m和n分别为它们的长度。L是一个二维数组,用于存储最长公共子序列的长度。在代码中,我们首先初始化L的第一行和第一列为0,然后从第二行和第二列开始,逐个比较X和Y的字符,如果它们相等,则L[i][j]等于L[i-1][j-1]+1,否则L[i][j]等于L[i-1][j]和L[i][j-1]中的较大值。最后返回L[m][n]即可得到最长公共子序列的长度。
相关问题
动态规划法实现最长公共子序列代码
下面是动态规划法实现最长公共子序列的代码:
```
#include <stdio.h>
#include <string.h>
char a[101], b[101];
char num[102][102]; //记录中间结果的数组
//动态规划采用二维数组来标识中间计算结果,避免重复的计算来提高效率
void LCS(int lena, int lenb) {
for (int i = 1; i <= lena; i++) {
for (int j = 1; j <= lenb; j++) {
if (a[i - 1] == b[j - 1]) { //注意这里的下标是i-1与j-1
num[i][j] = num[i - 1][j - 1] + 1;
} else {
num[i][j] = num[i][j - 1] > num[i - 1][j] ? num[i][j - 1] : num[i - 1][j];
}
}
}
}
int main() {
printf("请输入字符串a:");
scanf("%s", &a); //输入字符串
printf("请输入字符串b:");
scanf("%s", &b); //输入字符串
int lena = strlen(a); //获取字符串长度
int lenb = strlen(b);
memset(num, 0, sizeof(num)); //数组赋初值
LCS(lena, lenb);
printf("a和b的最长公共子序列长度为:%d", num[lena][lenb]);
return 0;
}
```
该代码使用了动态规划的思想,通过一个二维数组来记录中间计算结果,避免了重复计算,提高了效率。具体实现过程可以参考代码注释。
动态规划法求解最长公共子序列问题代码
以下是Python实现的最长公共子序列问题的动态规划算法代码:
```python
def lcs(X, Y):
# 创建一个二维数组,用于存储LCS的长度
m = len(X)
n = len(Y)
L = [[0] * (n + 1) for i in range(m + 1)]
# 填充LCS长度矩阵
for i in range(1, m+1):
for j in range(1, n+1):
if X[i-1] == Y[j-1]:
L[i][j] = L[i-1][j-1] + 1
else:
L[i][j] = max(L[i-1][j], L[i][j-1])
# LCS的长度即为L[m][n]
index = L[m][n]
# 从LCS长度矩阵中反向查找LCS
lcs = [""] * (index+1)
lcs[index] = ""
i = m
j = n
while i > 0 and j > 0:
if X[i-1] == Y[j-1]:
lcs[index-1] = X[i-1]
i -= 1
j -= 1
index -= 1
elif L[i-1][j] > L[i][j-1]:
i -= 1
else:
j -= 1
return "".join(lcs[1:])
```
其中,`X`和`Y`是要计算最长公共子序列的两个字符串。函数返回值是一个字符串,表示这两个字符串的最长公共子序列。