最长公共子序列问题C语言代码

最长公共子序列 (Longest Common Subsequence, LCS) 问题是计算机科学中经典的动态规划问题，它涉及找到两个输入字符串中最长的共同部分，但顺序可以不同。下面是使用C语言的一个简单递归版的解决方案：

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

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 max(int a, int b) {
    return (a > b) ? a : b;
}

int main() {
    char X[] = "ABCDGH";
    char Y[] = "AEDFHR";
    int m = strlen(X);
    int n = strlen(Y);

    printf("Length of LCS is %d", lcs(X, Y, m, n));

    return 0;
}

在这个代码中，`lcs`函数通过比较两个字符来递归地计算最长公共子序列长度。如果字符相等，则它们是当前LCS的一部分，并加上上一个字符对应的子序列长度；如果不相等，就取两个不包括当前字符的子串的最大LCS长度。