采用动态规划策略，用C++求解最长公共子序列问题，要求时间复杂度不超过O(m*n)，输出最长公共子序列

以下是C语言实现最长公共子序列的动态规划算法：

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

#define MAXLEN 100

int LCS[MAXLEN][MAXLEN];

void LCS_length(char *X, char *Y, int lenX, int lenY) {
    for (int i = 0; i <= lenX; i++) {
        for (int j = 0; j <= lenY; j++) {
            if (i == 0 || j == 0) {
                LCS[i][j] = 0;
            } else if (X[i-1] == Y[j-1]) {
                LCS[i][j] = LCS[i-1][j-1] + 1;
            } else {
                LCS[i][j] = LCS[i-1][j] > LCS[i][j-1] ? LCS[i-1][j] : LCS[i][j-1];
            }
        }
    }
}

void print_LCS(char *X, int lenX, int lenY) {
    char *LCS_str = (char*)malloc(sizeof(char) * (MAXLEN+1));
    int i = lenX, j = lenY, k = 0;
    while (i > 0 && j > 0) {
        if (X[i-1] == Y[j-1]) {
            LCS_str[k++] = X[i-1];
            i--;
            j--;
        } else if (LCS[i-1][j] >= LCS[i][j-1]) {
            i--;
        } else {
            j--;
        }
    }
    for (i = k-1; i >= 0; i--) {
        printf("%c", LCS_str[i]);
    }
    printf("\n");
    free(LCS_str);
}

int main() {
    char X[MAXLEN], Y[MAXLEN];
    printf("Please input two strings:\n");
    scanf("%s%s", X, Y);
    int lenX = strlen(X), lenY = strlen(Y);
    LCS_length(X, Y, lenX, lenY);
    printf("The length of LCS is: %d\n", LCS[lenX][lenY]);
    printf("The LCS is: ");
    print_LCS(X, lenX, lenY);
    return 0;
}

输入两个字符串，程序会计算它们的最长公共子序列的长度，并输出最长公共子序列。时间复杂度为O(m*n)，其中m和n分别为两个字符串的长度。