用 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数组的填充过程回溯原始字符串来构建子序列。