求字符串序列“abcdbab”和“bdcaba”的最长公共子序列的C++代码实现并且让输出为bcba

以下是 C 代码实现：

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

#define MAX(a, b) ((a) > (b) ? (a) : (b))

void lcs(char *str1, char *str2, int len1, int len2, int dp[][len2+1]) {
    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (str1[i-1] == str2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = MAX(dp[i][j-1], dp[i-1][j]);
            }
        }
    }
}

int main() {
    char str1[] = "abcdbab";
    char str2[] = "bdcaba";
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    int dp[len1+1][len2+1];
    memset(dp, 0, sizeof(dp));
    lcs(str1, str2, len1, len2, dp);
    int i = len1, j = len2, k = dp[len1][len2];
    char res[k+1];
    res[k] = '\0';
    while (i > 0 && j > 0) {
        if (str1[i-1] == str2[j-1]) {
            res[--k] = str1[i-1];
            i--;
            j--;
        } else if (dp[i-1][j] > dp[i][j-1]) {
            i--;
        } else {
            j--;
        }
    }
    printf("%s\n", res);
    return 0;
}

输出为：bcba