用c语言求字符串序列“ABCDBAB”和“BDCABA”的最长公共子序列

这是一个经典的问题，有多种解决方法。一种常见的方法是使用动态规划算法。

具体来说，我们可以定义一个二维数组L，其中L[i][j]表示字符串序列1的前i个字符与字符串序列2的前j个字符的最长公共子序列长度。然后，我们可以按照以下递推式来计算L数组的值：

L[i][j] = 0 (i = 0 或 j = 0)
L[i][j] = L[i-1][j-1] + 1 (sequence1[i] = sequence2[j])
L[i][j] = max(L[i][j-1], L[i-1][j]) (sequence1[i] != sequence2[j])

最终，L[m][n]就是要求的最长公共子序列长度，其中m和n分别是两个字符串序列的长度。我们可以根据L数组求出最长公共子序列本身。

在这个例子中，当使用动态规划算法时，得到的最长公共子序列是“BDAB”，长度为4。

相关问题

用 c语言求字符串序列“ABCDBAB”和“BDCABA”的最长公共子序列

在C语言中，可以使用动态规划(Dynamic Programming)的方法来计算两个字符串的最长公共子序列(LCS，Longest Common Subsequence)。这里我们可以创建一个二维数组来存储每个位置的最长公共子序列长度。

首先，定义两个输入字符串，例如 "ABCDBAB" 和 "BDCABA"，然后初始化一个大小为 (m+1) x (n+1)，其中 m 和 n 分别是这两个字符串的长度，因为需要额外一列和一行用于边界处理。

遍历两个字符串，对于每个字符，如果它们相等，则当前字符计入LCS，将上一个位置的LCS加一；如果不相等，选择前一个字符的LCS值。最后数组的右下角元素即为整个字符串的最长公共子序列的长度。

以下是伪代码示例：

int LCS(char str1[], char str2[], int m, int n)
{
   int dp[m + 1][n + 1];

   // 初始化第一行和第一列
   for (int i = 0; i <= m; i++)
       dp[i][0] = 0;
   for (int j = 0; j <= n; j++)
       dp[0][j] = 0;

   // 动态填充dp数组
   for (int i = 1; i <= m; i++) {
      for (int j = 1; j <= n; j++) {
         if (str1[i - 1] == str2[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];
}

实际应用中，你可以定义相应的函数，并在循环结束后返回dp[m][n]作为结果。需要注意的是，这个算法不会直接给出最长公共子序列本身，你需要根据dp数组的填充过程回溯原始字符串来构建子序列。

用C语言实现，求字符串序列“ABCDBAB”和“BDCABA”的最长公共子序列

可以使用动态规划算法来解决这个问题。具体步骤如下：

1. 定义一个二维数组dp[m+1][n+1]，其中m和n分别为两个字符串的长度。

2. 初始化dp数组，将第一行和第一列都设为0。

3. 遍历两个字符串，如果当前字符相同，则dp[i][j] = dp[i-1][j-1] + 1；否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

4. 最后，dp[m][n]就是最长公共子序列的长度。

根据上述算法，可以得到字符串序列“ABCDBAB”和“BDCABA”的最长公共子序列为“BCBA”，长度为4。

以下是C语言的代码实现：

#include <stdio.h>
#include <string.h>

#define MAX_LEN 100

int max(int a, int b) {
return a > b ? a : b;
}

int lcs(char* str1, char* str2) {
int m = strlen(str1);
int n = strlen(str2);
int dp[MAX_LEN][MAX_LEN];
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 (str1[i-1] == str2[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 str1[] = "ABCDBAB";
char str2[] = "BDCABA";
int len = lcs(str1, str2);
printf("The length of the longest common subsequence is %d\n", len);
return 0;
}