用C++代码动态规划解决最长公共子序列问题 要求 给出两个字符序列 输出最长公共子序列的长度 和所有的最长公共子序列 当最长公共子序列为空时，输出最长公共子序列长度为0，最长公共子序列为：None。 【样例1输入】 A B C B D A B B D C A B A 【样例1输出】 4 BCBA BDAB

好的，以下是C++代码实现动态规划解决最长公共子序列问题：

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int MAX_N = 1000;

int dp[MAX_N][MAX_N]; // dp数组
char str1[MAX_N]; // 输入的第一个字符序列
char str2[MAX_N]; // 输入的第二个字符序列
vector<string> res; // 存储所有最长公共子序列的数组

int main() {
    cin >> str1 >> str2;

    int len1 = strlen(str1);
    int len2 = strlen(str2);

    // 初始化dp数组
    for (int i = 0; i <= len1; i++) {
        dp[i][0] = 0;
    }
    for (int j = 0; j <= len2; j++) {
        dp[0][j] = 0;
    }

    // 动态规划
    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 - 1][j], dp[i][j - 1]);
            }
        }
    }

    // 输出最长公共子序列长度
    cout << dp[len1][len2] << endl;

    // 输出所有最长公共子序列
    string temp;
    int i = len1, j = len2;
    while (i > 0 && j > 0) {
        if (str1[i - 1] == str2[j - 1]) { // 字符相等，加入temp中
            temp += str1[i - 1];
            i--;
            j--;
        } else if (dp[i - 1][j] >= dp[i][j - 1]) { // 上方的元素大于左方的元素，向上移动
            i--;
        } else if (dp[i - 1][j] <= dp[i][j - 1]) { // 左方的元素大于上方的元素，向左移动
            j--;
        }
    }

    if (temp.empty()) { // 最长公共子序列为空
        cout << "None" << endl;
    } else {
        string res_temp(temp.rbegin(), temp.rend()); // 翻转temp
        cout << res_temp << endl;
        res.push_back(res_temp); // 存入res中

        // 找到其他最长公共子序列
        while (i > 0 && j > 0) {
            if (str1[i - 1] == str2[j - 1]) { // 字符相等，加入temp中
                temp += str1[i - 1];
                i--;
                j--;
            } else if (dp[i - 1][j] >= dp[i][j - 1]) { // 上方的元素大于左方的元素，向上移动
                i--;
            } else if (dp[i - 1][j] <= dp[i][j - 1]) { // 左方的元素大于上方的元素，向左移动
                j--;
            }

            if (i == 0 || j == 0) { // 到达边界，将temp翻转并存入res中
                string res_temp(temp.rbegin(), temp.rend());
                res.push_back(res_temp);
            }
        }

        // 输出所有最长公共子序列
        for (int i = 1; i < res.size(); i++) {
            cout << res[i] << endl;
        }
    }

    return 0;
}

输入样例：A B C B D A B B D C A B A

输出样例：4 BCBA BDAB