动态规划最长公共子序列的伪代码
时间: 2024-01-07 18:23:43 浏览: 40
动态规划最长公共子序列的伪代码如下:
```
function LCS(X, Y):
m = length(X)
n = length(Y)
c = array[m+1][n+1]
for i = 0 to m:
c[i][0] = 0
for j = 0 to n:
c[0][j] = 0
for i = 1 to m:
for j = 1 to n:
if X[i] == Y[j]:
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]
```
其中,X和Y分别表示两个序列,m和n分别表示两个序列的长度。c[i][j]表示的是序列X的前i个元素和序列Y的前j个元素的最长公共子序列的长度。
相关问题
c语言最长公共子序列伪代码
以下是C语言求解最长公共子序列的伪代码:
1. 首先定义一个函数Lcs_length,该函数接受两个字符串str1和str2以及两个指向指针的指针c和b作为参数,其中c和b用于存储最长公共子序列的长度和路径信息。
2. 在Lcs_length函数中,首先获取str1和str2的长度,然后创建一个二维数组c,用于存储最长公共子序列的长度,以及一个二维数组b,用于存储路径信息。
3. 然后使用两个for循环遍历str1和str2的所有字符,如果当前字符相同,则将c[i][j]设置为c[i-1][j-1]+1,并将b[i][j]设置为左上角。
4. 如果当前字符不同,则将c[i][j]设置为max(c[i-1][j], c[i][j-1]),并将b[i][j]设置为c[i-1][j] > c[i][j-1] ? 上方 : 左方。
5. 最后返回c和b。
6. 定义一个函数Find_Lcs,该函数接受两个字符串str1和str2作为参数。
7. 在Find_Lcs函数中,首先调用Lcs_length函数获取最长公共子序列的长度和路径信息。
8. 然后根据路径信息,倒序遍历c数组,将最长公共子序列存储到一个字符数组中。
9. 最后输出最长公共子序列的长度和内容。
```c
// 定义Lcs_length函数
int Lcs_length(char *str1, char *str2, int **c, int **b) {
int len1 = strlen(str1);
int len2 = strlen(str2);
int i, j;
for (i = 0; i <= len1; i++) {
c[i][0] = 0;
}
for (j = 0; j <= len2; j++) {
c[0][j] = 0;
}
for (i = 1; i <= len1; i++) {
for (j = 1; j <= len2; j++) {
if (str1[i-1] == str2[j-1]) {
c[i][j] = c[i-1][j-1] + 1;
b[i][j] = 0;
} else if (c[i-1][j] >= c[i][j-1]) {
c[i][j] = c[i-1][j];
b[i][j] = 1;
} else {
c[i][j] = c[i][j-1];
b[i][j] = -1;
}
}
}
return c[len1][len2];
}
// 定义Find_Lcs函数
void Find_Lcs(char *str1, char *str2) {
int len1 = strlen(str1);
int len2 = strlen(str2);
int **c = (int **)malloc((len1+1) * sizeof(int *));
int **b = (int **)malloc((len1+1) * sizeof(int *));
int i, j;
for (i = 0; i <= len1; i++) {
c[i] = (int *)malloc((len2+1) * sizeof(int));
b[i] = (int *)malloc((len2+1) * sizeof(int));
}
int len = Lcs_length(str1, str2, c, b);
char *lcs = (char *)malloc((len+1) * sizeof(char));
lcs[len] = '\0';
i = len1;
j = len2;
while (i > 0 && j > 0) {
if (b[i][j] == 0) {
lcs[--len] = str1[i-1];
i--;
j--;
} else if (b[i][j] == 1) {
i--;
} else {
j--;
}
}
printf("最长公共子序列长度为:%d\n", len);
printf("最长公共子序列为:%s\n", lcs);
free(lcs);
for (i = 0; i <= len1; i++) {
free(c[i]);
free(b[i]);
}
free(c);
free(b);
}
```
最长公共子序列的伪代码
以下是最长公共子序列(Longest Common Subsequence,LCS)的伪代码:
输入:字符串A和字符串B,长度分别为m和n
输出:最长公共子序列的长度和该子序列
1. 初始化一个(m+1) * (n+1)的矩阵dp,全部赋值为0
2. for i in range(1, m+1):
for j in range(1, n+1):
if A[i-1] == B[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
3. lcs_len = dp[m][n]
4. 初始化一个空序列lcs
5. while lcs_len > 0:
if A[m-1] == B[n-1]:
lcs.append(A[m-1])
m -= 1
n -= 1
lcs_len -= 1
elif dp[m-1][n] >= dp[m][n-1]:
m -= 1
else:
n -= 1
6. 将lcs序列反转,得到最长公共子序列
解释:首先,创建一个二维的dp数组,用来存储最长公共子序列的长度。然后,我们遍历字符串A和B中的所有字符,如果字符相同,则在dp[i][j]中存储dp[i-1][j-1]+1,表示当前字符在最长公共子序列中。如果字符不同,则在dp[i][j]中存储max(dp[i-1][j], dp[i][j-1]),表示当前字符不在最长公共子序列中,需要在A前缀和B前缀的子序列中寻找最长公共子序列。最终,我们可以通过回溯dp数组,构造出最长公共子序列。