求解最长公共子序列问题,给出最优值和最优解,并通过实例验证： 1、用自顶向下方式求解 2、用自底向上方式求解， 3、尝试找到不同的最优解。全部使用C++实现

1. 自顶向下方式求解最长公共子序列问题

首先，我们需要定义一个递归函数来解决最长公共子序列问题，并将其存储在一个表中，以避免重复计算。

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

#define MAX_LEN 100

int lcs_table[MAX_LEN + 1][MAX_LEN + 1];

int lcs_recursive(char* s1, char* s2, int m, int n) {
    if (m == 0 || n == 0) {
        return 0;
    }

    if (lcs_table[m][n] != -1) {
        return lcs_table[m][n];
    }

    if (s1[m - 1] == s2[n - 1]) {
        lcs_table[m][n] = 1 + lcs_recursive(s1, s2, m - 1, n - 1);
    } else {
        int len1 = lcs_recursive(s1, s2, m - 1, n);
        int len2 = lcs_recursive(s1, s2, m, n - 1);
        lcs_table[m][n] = (len1 > len2) ? len1 : len2;
    }

    return lcs_table[m][n];
}

int main() {
    memset(lcs_table, -1, sizeof(lcs_table));

    char* s1 = "ACCGGTCGAGTGCGCGGAAGCCGGCCGAA";
    char* s2 = "GTCGTTCGGAATGCCGTTGCTCTGTAAA";

    int m = strlen(s1);
    int n = strlen(s2);

    int len = lcs_recursive(s1, s2, m, n);

    printf("The length of the longest common subsequence is %d\n", len);

    return 0;
}

2. 自底向上方式求解最长公共子序列问题

在这种方法中，我们将解决方案从小规模的子问题中构建出来。我们可以使用一个二维表来存储最长公共子序列的长度。

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

#define MAX_LEN 100

int lcs_table[MAX_LEN + 1][MAX_LEN + 1];

int lcs_bottom_up(char* s1, char* s2, int m, int n) {
    int i, j;

    for (i = 0; i <= m; i++) {
        for (j = 0; j <= n; j++) {
            if (i == 0 || j == 0) {
                lcs_table[i][j] = 0;
            } else if (s1[i - 1] == s2[j - 1]) {
                lcs_table[i][j] = 1 + lcs_table[i - 1][j - 1];
            } else {
                int len1 = lcs_table[i - 1][j];
                int len2 = lcs_table[i][j - 1];
                lcs_table[i][j] = (len1 > len2) ? len1 : len2;
            }
        }
    }

    return lcs_table[m][n];
}

int main() {
    memset(lcs_table, -1, sizeof(lcs_table));

    char* s1 = "ACCGGTCGAGTGCGCGGAAGCCGGCCGAA";
    char* s2 = "GTCGTTCGGAATGCCGTTGCTCTGTAAA";

    int m = strlen(s1);
    int n = strlen(s2);

    int len = lcs_bottom_up(s1, s2, m, n);

    printf("The length of the longest common subsequence is %d\n", len);

    return 0;
}

3. 寻找不同的最优解

在最长公共子序列问题中，可能存在多个相同长度的最长公共子序列。要找到不同的最优解，我们可以修改递归函数，使其返回最长公共子序列本身，而不仅仅是其长度。

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

#define MAX_LEN 100

char lcs_table[MAX_LEN + 1][MAX_LEN + 1];

char* lcs_recursive(char* s1, char* s2, int m, int n) {
    if (m == 0 || n == 0) {
        return "";
    }

    if (lcs_table[m][n] != 0) {
        return lcs_table[m][n];
    }

    if (s1[m - 1] == s2[n - 1]) {
        char* lcs = lcs_recursive(s1, s2, m - 1, n - 1);
        char* result = (char*)malloc(strlen(lcs) + 2);
        sprintf(result, "%s%c", lcs, s1[m - 1]);
        lcs_table[m][n] = result;
    } else {
        char* lcs1 = lcs_recursive(s1, s2, m - 1, n);
        char* lcs2 = lcs_recursive(s1, s2, m, n - 1);
        lcs_table[m][n] = (strlen(lcs1) > strlen(lcs2)) ? lcs1 : lcs2;
    }

    return lcs_table[m][n];
}

int main() {
    memset(lcs_table, 0, sizeof(lcs_table));

    char* s1 = "ACCGGTCGAGTGCGCGGAAGCCGGCCGAA";
    char* s2 = "GTCGTTCGGAATGCCGTTGCTCTGTAAA";

    int m = strlen(s1);
    int n = strlen(s2);

    char* lcs = lcs_recursive(s1, s2, m, n);

    printf("The longest common subsequence is %s\n", lcs);

    return 0;
}