最长公共子序列穷举法C语言

最长公共子序列（Longest Common Subsequence，简称LCS）是指在两个序列中找到最长的公共子序列的问题。穷举法是一种解决LCS问题的方法之一，下面是使用C语言实现的简单介绍：

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

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

int lcs(char* X, char* Y, int m, int n) {
    if (m == 0 || n == 0)
        return 0;
    if (X[m - 1] == Y[n - 1])
        return 1 + lcs(X, Y, m - 1, n - 1);
    else
        return max(lcs(X, Y, m, n - 1), lcs(X, Y, m - 1, n));
}

int main() {
    char X[] = "ABCDEF";
    char Y[] = "ABDCEF";
    int m = strlen(X);
    int n = strlen(Y);
    printf("最长公共子序列的长度为：%d\n", lcs(X, Y, m, n));
    return 0;
}

上述代码中，`lcs`函数使用递归的方式计算最长公共子序列的长度。其中，`X`和`Y`分别表示两个序列，`m`和`n`分别表示两个序列的长度。`max`函数用于比较两个数的大小，返回较大的值。

运行上述代码，输出结果为：

最长公共子序列的长度为：4