题目描述 若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B} 是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。 给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。 给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。 输入 输入包括两行，每行表示一个字符串。 输出 输出只有一个字符串，表示最大公共子序列。 样例输入 abcbdab bfcdgbe 样例输出 bcdb用c语言写代码

以下是使用动态规划算法求解最长公共子序列的C语言代码：

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

#define MAX_LEN 1000

int dp[MAX_LEN][MAX_LEN];

int main() {
    char X[MAX_LEN], Y[MAX_LEN], lcs[MAX_LEN];
    scanf("%s %s", X, Y);
    int m = strlen(X), n = strlen(Y);
    // 初始化dp数组
    for (int i = 0; i <= m; i++) {
        dp[i][0] = 0;
    }
    for (int j = 0; j <= n; j++) {
        dp[0][j] = 0;
    }
    // 动态规划求解
    for (int i = 1; i <= m; i++) {
        for (int 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] = (dp[i-1][j] > dp[i][j-1]) ? dp[i-1][j] : dp[i][j-1];
            }
        }
    }
    // 根据dp数组反向追溯最长公共子序列
    int len = dp[m][n];
    int i = m, j = n;
    while (len > 0) {
        if (X[i-1] == Y[j-1]) {
            lcs[len-1] = X[i-1];
            i--;
            j--;
            len--;
        } else if (dp[i-1][j] > dp[i][j-1]) {
            i--;
        } else {
            j--;
        }
    }
    printf("%s\n", lcs);
    return 0;
}

这段代码中，先读入两个字符串X和Y，然后按照上面提到的状态转移方程进行动态规划求解，最后根据dp数组反向追溯得到最长公共子序列。输出结果即为最长公共子序列。