求最长公共子序列c语言实现

求最长公共子序列（Longest Common Subsequence，LCS）是指两个序列中最长的相同子序列的长度。在C语言中，你可以通过动态规划（Dynamic Programming）的方式来解决这个问题。这里是一个简单的递归版和迭代版的C语言实现：

### 递归版本（不推荐，效率低）

#include <stdio.h>
#define MAX_LEN 100

int lcs(char *X, char *Y, int m, int n) {
    if (m == 0 || n == 0)
        return 0;
    else 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[] = "ABCBDAB";
    char Y[] = "BDCAB";
    int m = strlen(X);
    int n = strlen(Y);
    printf("Length of LCS is %d\n", lcs(X, Y, m, n));
    return 0;
}

### 迭代版本（更常用，效率高）

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

int lcs_iterative(char *X, char *Y, int m, int n) {
    int dp[MAX_LEN][MAX_LEN] = {0};
    int i, j;

    for (i = 1; i <= m; i++) {
        for (j = 1; j <= n; j++) {
            if (X[i - 1] == Y[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 X[] = "ABCBDAB";
    char Y[] = "BDCAB";
    int m = strlen(X);
    int n = strlen(Y);
    printf("Length of LCS is %d\n", lcs_iterative(X, Y, m, n));
    return 0;
}