用动态规划法求解最长公共子序列问题。C++代码实现

最长公共子序列（Longest Common Subsequence, LCS）问题是一个经典的计算机科学问题，通常通过动态规划来解决。动态规划的主要思想是将原问题分解成更小的子问题，并存储每个子问题的结果以避免重复计算。

以下是使用C++实现的简单动态规划算法：

#include <vector>

int lcs(std::string X, std::string Y) {
    int m = X.size(), n = Y.size();
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (X[i - 1] == Y[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    // 最长公共子序列的长度即最后一行的最后一列
    return dp[m][n];
}

std::string longestCommonSubseq(std::string X, std::string Y) {
    int length = lcs(X, Y);
    std::vector<char> result(length, '\0');
    
    // 从右下角开始回溯构建LCS
    int i = X.size(), j = Y.size();
    while (i > 0 && j > 0) {
        if (X[i - 1] == Y[j - 1]) {
            result[length - 1] = X[i - 1]; // 取得当前字符并倒序
            i--;
            j--;
            length--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }
    
    return std::string(result.rbegin(), result.rend());
}