2.用动态规划算法解决最长公共子序列问题c/c++

最长公共子序列（Longest Common Subsequence，LCS）问题是计算机科学中经典的动态规划问题之一。它旨在找到两个给定序列中最长的共同子序列，而不需要它们在相同的位置上出现。下面是用C++实现动态规划求解LCS的一个简单例子：

#include <iostream>
#include <vector>

std::string lcs(std::string X, std::string Y) {
    int m = X.length();
    int n = Y.length();
    
    // 初始化一个二维动态规划数组
    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]);
            }
        }
    }
    
    // 从dp矩阵的右下角开始回溯构建LCS字符串
    std::string result;
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (X[i - 1] == Y[j - 1]) {
            result += X[i - 1];
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }
    
    return result;
}

int main() {
    std::string X = "ABCDGH";
    std::string Y = "AEDFHR";
    std::cout << "Longest common subsequence: " << lcs(X, Y) << std::endl;
    return 0;
}

在这个代码中，`dp[i][j]`表示`X`的前`i`个字符和`Y`的前`j`个字符的最长公共子序列的长度。如果`X[i-1]`等于`Y[j-1]`，说明当前字符可以添加到最长公共子序列中，否则选择前面子串中的较长一个。最后，通过回溯`dp`数组构建出实际的LCS。