c语言最长公共子序列自顶向下和自底向上
时间: 2024-06-18 07:05:28 浏览: 18
最长公共子序列(Longest Common Subsequence,简称LCS)是指两个或多个序列中的最长公共子序列,可以使用动态规划求解。
自顶向下的方法也被称为记忆化搜索,它使用递归来实现。我们将问题划分为子问题,并将其存储在一个数组中。在计算过程中,先检查存储的数组是否有对应的值,如果没有,则计算它并将其存储在数组中,然后返回该值。这种方法可以避免重复计算相同的子问题,从而提高计算效率。
自底向上的方法是一种迭代的方法,它从较小的子问题开始,逐步解决大问题。我们首先计算最短的子序列,然后使用这些结果来计算更长的子序列。我们需要一个二维数组来存储每个子序列的最长公共子序列长度。在计算过程中,我们将数组填满,直到获得整个序列的最长公共子序列。
总体来说,这两种方法的思路类似,但具体实现方式略有不同。自顶向下的方法可以避免重复计算,但需要使用递归和数组来存储计算结果;自底向上的方法则可以避免递归和数组,但需要使用循环和二维数组来存储计算结果。
相关问题
c语言最长公共子序列自顶向下和自底向上代码
C语言中求解最长公共子序列可以使用动态规划算法,其中自顶向下和自底向上是两种不同的实现方式。
自顶向下的代码实现:
```
#include <stdio.h>
#include <string.h>
#define MAXLEN 100
int lcs(char *str1, char *str2, int m, int n, int memo[][MAXLEN]) {
if (m == 0 || n == 0) {
return 0;
}
if (memo[m-1] != -1) {
return memo[m-1][n-1];
}
if (str1[m-1] == str2[n-1]) {
memo[m-1][n-1] = 1 + lcs(str1, str2, m-1, n-1, memo);
} else {
memo[m-1][n-1] = (lcs(str1, str2, m, n-1, memo) > lcs(str1, str2, m-1, n, memo)) ? lcs(str1, str2, m, n-1, memo) : lcs(str1, str2, m-1, n, memo);
}
return memo[m-1][n-1];
}
int main() {
char str1[MAXLEN], str2[MAXLEN];
int m, n;
scanf("%s", str1);
scanf("%s", str2);
m = strlen(str1);
n = strlen(str2);
int memo[MAXLEN][MAXLEN];
memset(memo, -1, sizeof(memo));
printf("The length of the longest common subsequence is %d\n", lcs(str1, str2, m, n, memo));
return 0;
}
```
自底向上的代码实现:
```
#include <stdio.h>
#include <string.h>
#define MAXLEN 100
int lcs(char *str1, char *str2) {
int m = strlen(str1);
int n = strlen(str2);
int memo[MAXLEN][MAXLEN];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
memo[i][j] = 0;
} else if (str1[i-1] == str2[j-1]) {
memo[i][j] = 1 + memo[i-1][j-1];
} else {
memo[i][j] = (memo[i][j-1] > memo[i-1][j]) ? memo[i][j-1] : memo[i-1][j];
}
}
}
return memo[m][n];
}
int main() {
char str1[MAXLEN], str2[MAXLEN];
scanf("%s", str1);
scanf("%s", str2);
printf("The length of the longest common subsequence is %d\n", lcs(str1, str2));
return 0;
}
```
C语言用自底向上方式求解最长公共子序列问题
C语言中求解最长公共子序列问题的自底向上方式是通过动态规划实现的。具体步骤如下:
1. 定义一个二维数组dp[m+1][n+1],其中m和n分别为两个字符串的长度。
2. 初始化第一行和第一列的值为0。
3. 从第二行和第二列开始,依次计算dp[i][j]的值。如果字符串1中第i个字符和字符串2中第j个字符相等,则dp[i][j]等于dp[i-1][j-1]+1;否则,dp[i][j]等于dp[i-1][j]和dp[i][j-1]中的较大值。
4. 最终dp[m][n]的值即为两个字符串的最长公共子序列长度。
下面是C语言代码实现:
```c
#include <stdio.h>
#include <string.h>
int max(int a, int b) {
return a > b ? a : b;
}
int lcs(char *s1, char *s2) {
int m = strlen(s1);
int n = strlen(s2);
int dp[m+1][n+1];
int i, j;
for (i = 0; i <= m; i++) {
dp[i][0] = 0;
}
for (j = 0; j <= n; j++) {
dp[0][j] = 0;
}
for (i = 1; i <= m; i++) {
for (j = 1; j <= n; j++) {
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]);
}
}
}
return dp[m][n];
}
int main() {
char s1[] = "ABCD";
char s2[] = "ACDF";
int len = lcs(s1, s2);
printf("%d\n", len);
return 0;
}
```
输出结果为3,即最长公共子序列为ACD。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)