C语言分别用动态规划算法和递归算法求最长公共子序列并输出最长公共子序列

当使用动态规划算法和递归算法来求解最长公共子序列（Longest Common Subsequence）时，可以按照以下步骤进行实现：

1. 动态规划算法（Dynamic Programming）：

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

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

void printLCS(char *str1, char *str2, int m, int n, int dp[m+1][n+1]) {
    int length = dp[m][n];
    char lcs[length + 1];
    lcs[length] = '\0';

    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (str1[i - 1] == str2[j - 1]) {
            lcs[length - 1] = str1[i - 1];
            i--;
            j--;
            length--;
        }
        else if (dp[i-1][j] > dp[i][j-1]) {
            i--;
        }
        else {
            j--;
        }
    }

    printf("Longest Common Subsequence: %s\n", lcs);
}

void LCS(char *str1, char *str2) {
    int m = strlen(str1);
    int n = strlen(str2);
    int dp[m+1][n+1];

    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            }
            else if (str1[i - 1] == str2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }

    printLCS(str1, str2, m, n, dp);
}

int main() {
    char str1[] = "AGGTAB";
    char str2[] = "GXTXAYB";

    LCS(str1, str2);

    return 0;
}

2. 递归算法：

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

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

void printLCS(char *str1, char *str2, int m, int n, int dp[m+1][n+1]) {
    if (m == 0 || n == 0) {
        return;
    }

    if (str1[m - 1] == str2[n - 1]) {
        printLCS(str1, str2, m - 1, n - 1, dp);
        printf("%c", str1[m - 1]);
    }
    else if (dp[m-1][n] > dp[m][n-1]) {
        printLCS(str1, str2, m - 1, n, dp);
    }
    else {
        printLCS(str1, str2, m, n - 1, dp);
    }
}

int LCS(char *str1, char *str2, int m, int n) {
    if (m == 0 || n == 0) {
        return 0;
    }

    if (str1[m - 1] == str2[n - 1]) {
        return 1 + LCS(str1, str2, m - 1, n - 1);
    }
    else {
        return max(LCS(str1, str2, m - 1, n), LCS(str1, str2, m, n - 1));
    }
}

int main() {
    char str1[] = "AGGTAB";
    char str2[] = "GXTXAYB";
    int m = strlen(str1);
    int n = strlen(str2);
    int dp[m+1][n+1];

    int lcsLength = LCS(str1, str2, m, n);

    printf("Longest Common Subsequence Length: %d\n", lcsLength);

    printLCS(str1, str2, m, n, dp);

    return 0;
}

这样，你就可以使用动态规划算法和递归算法求解最长公共子序列，并输出最长公共子序列。