最长公共子序列问题。给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，用动态规划算法找出X和Y的最长公共子序列，用C/C++实现该算法。

下面是C语言实现最长公共子序列问题的代码，采用动态规划算法：

#include <stdio.h>
#include <string.h>
#define MAXLEN 100

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

int LCS(char X[], char Y[], int m, int n, int c[][MAXLEN], int b[][MAXLEN]) {
    int i, j;
    for (i = 0; i <= m; i++) {
        c[i][0] = 0;
    }
    for (j = 0; j <= n; j++) {
        c[0][j] = 0;
    }
    for (i = 1; i <= m; i++) {
        for (j = 1; j <= n; j++) {
            if (X[i - 1] == Y[j - 1]) {
                c[i][j] = c[i - 1][j - 1] + 1;
                b[i][j] = 0; // 记录方向，0表示左上
            } else if (c[i - 1][j] >= c[i][j - 1]) {
                c[i][j] = c[i - 1][j];
                b[i][j] = 1; // 记录方向，1表示上
            } else {
                c[i][j] = c[i][j - 1];
                b[i][j] = -1; // 记录方向，-1表示左
            }
        }
    }
    return c[m][n];
}

void printLCS(char X[], int b[][MAXLEN], int i, int j) {
    if (i == 0 || j == 0) {
        return;
    }
    if (b[i][j] == 0) {
        printLCS(X, b, i - 1, j - 1);
        printf("%c", X[i - 1]);
    } else if (b[i][j] == 1) {
        printLCS(X, b, i - 1, j);
    } else {
        printLCS(X, b, i, j - 1);
    }
}

int main() {
    char X[MAXLEN], Y[MAXLEN];
    int c[MAXLEN][MAXLEN], b[MAXLEN][MAXLEN];
    int m, n, lcslen;
    printf("请输入序列X：");
    scanf("%s", X);
    printf("请输入序列Y：");
    scanf("%s", Y);
    m = strlen(X);
    n = strlen(Y);
    lcslen = LCS(X, Y, m, n, c, b);
    printf("最长公共子序列长度为：%d\n", lcslen);
    printf("最长公共子序列为：");
    printLCS(X, b, m, n);
    printf("\n");
    return 0;
}

运行结果：

请输入序列X：ABCBDAB
请输入序列Y：BDCABA
最长公共子序列长度为：4
最长公共子序列为：BCBA