用C++代码解决问题 【问题描述】使用动态规划算法解最长公共子序列问题，具体来说就是，依据其递归式自底向上的方式依次计算得到每个子问题的最优值。 输入两段字符串 ，输出最长公共子序列的长度和所有最优子公共序列的情况 【样例1输入】 A B C B D A B B D C A B A 【样例1输出】 4 BCBA BDAB

以下是对应的C++代码实现：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

void LCS(string S1, string S2)
{
    int m = S1.size();
    int n = S2.size();

    // 构建二维数组存储LCS的长度
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    // 计算LCS的长度
    for (int i = 1; i <= m; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            if (S1[i - 1] == S2[j - 1])
            {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else
            {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    int len = dp[m][n];  // 最长公共子序列的长度

    // 构造所有最优子公共序列
    vector<string> res;
    string cur;
    int i = m, j = n;
    while (i > 0 && j > 0)
    {
        if (S1[i - 1] == S2[j - 1])
        {
            cur.push_back(S1[i - 1]);
            --i;
            --j;
        }
        else if (dp[i - 1][j] >= dp[i][j - 1])
        {
            --i;
        }
        else
        {
            --j;
        }

        if (cur.size() == len)
        {
            res.push_back(cur);
            cur.clear();
        }
    }

    // 输出结果
    cout << len << " ";
    for (auto it = res.rbegin(); it != res.rend(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;
}

int main()
{
    string S1, S2;
    cin >> S1 >> S2;

    LCS(S1, S2);

    return 0;
}

代码思路：

首先定义一个二维数组 `dp`，其中 `dp[i][j]` 表示 `S1` 的前 `i` 个字符和 `S2` 的前 `j` 个字符的最长公共子序列的长度。

如果 `S1[i-1]` 等于 `S2[j-1]`，则 `dp[i][j] = dp[i-1][j-1] + 1`，表示当前字符是公共字符，并且计入最长公共子序列的长度；否则，`dp[i][j]` 取 `dp[i-1][j]` 和 `dp[i][j-1]` 中的最大值，表示当前字符不在最长公共子序列中。

计算完 `dp` 数组后，我们可以通过逆推得到所有最优子公共序列。具体地，从 `dp[m][n]` 开始，如果 `S1[i-1]` 等于 `S2[j-1]`，则当前字符是最优解的一部分，并且需要往左上角继续逆推；否则，如果 `dp[i-1][j]` 大于等于 `dp[i][j-1]`，则往上逆推；否则，往左逆推。当逆推得到的字符串长度等于最长公共子序列的长度时，将其加入结果中。

最后输出最长公共子序列的长度和所有最优子公共序列即可。