1.完成任意两个字符串的最长公共子序列的计算，输出最长公共子序列及其长度 2.对算法进行改进 如果只需要计算最长公共子序列的长度，在计算c[i][j]时，只用到数组c的第i行和第i-1行。因此，用2行的数组空间就可以计算出最长公共子序列的长度。C语言代码加注释

1. 计算任意两个字符串的最长公共子序列及其长度：

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

#define MAXLEN 100

void LCS(char *s1, char *s2, int len1, int len2, char *lcs, int *len) {
    int i, j;
    int c[MAXLEN][MAXLEN] = {0};
    // 计算最长公共子序列的长度
    for (i = 1; i <= len1; i++) {
        for (j = 1; j <= len2; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                c[i][j] = c[i - 1][j - 1] + 1;
            } else if (c[i - 1][j] >= c[i][j - 1]) {
                c[i][j] = c[i - 1][j];
            } else {
                c[i][j] = c[i][j - 1];
            }
        }
    }
    // 从 c 数组中取出最长公共子序列
    i = len1;
    j = len2;
    int index = c[len1][len2];
    while (i > 0 && j > 0) {
        if (s1[i - 1] == s2[j - 1]) {
            lcs[index - 1] = s1[i - 1];
            i--;
            j--;
            index--;
        } else if (c[i - 1][j] >= c[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }
    *len = c[len1][len2];
}

int main() {
    char s1[MAXLEN], s2[MAXLEN], lcs[MAXLEN];
    int len1, len2, len;
    printf("输入字符串1：\n");
    scanf("%s", s1);
    printf("输入字符串2：\n");
    scanf("%s", s2);
    len1 = strlen(s1);
    len2 = strlen(s2);
    LCS(s1, s2, len1, len2, lcs, &len);
    printf("最长公共子序列为：\n%s\n", lcs);
    printf("最长公共子序列长度为：%d\n", len);
    return 0;
}

2. 改进后的计算最长公共子序列长度的算法：

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

#define MAXLEN 100

void LCS(char *s1, char *s2, int len1, int len2, int *len) {
    int i, j;
    int c[2][MAXLEN] = {0};
    // 计算最长公共子序列的长度
    for (i = 1; i <= len1; i++) {
        for (j = 1; j <= len2; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                c[1][j] = c[0][j - 1] + 1;
            } else if (c[0][j] >= c[1][j - 1]) {
                c[1][j] = c[0][j];
            } else {
                c[1][j] = c[1][j - 1];
            }
        }
        memcpy(c[0], c[1], sizeof(c[1]));
    }
    *len = c[1][len2];
}

int main() {
    char s1[MAXLEN], s2[MAXLEN];
    int len1, len2, len;
    printf("输入字符串1：\n");
    scanf("%s", s1);
    printf("输入字符串2：\n");
    scanf("%s", s2);
    len1 = strlen(s1);
    len2 = strlen(s2);
    LCS(s1, s2, len1, len2, &len);
    printf("最长公共子序列长度为：%d\n", len);
    return 0;
}