动态规划——最长公共子序列c++代码

动态规划是一种解决复杂问题的算法思想，通常用于优化具有重叠子问题和最优子结构的问题，如寻找最长公共子序列（Longest Common Subsequence, LCS）。最长公共子序列是指两个序列中的最长子序列，但顺序不一定要相同。

在C++中，可以使用二维数组来实现动态规划求解最长公共子序列。以下是一个简单的C++代码示例：

#include <iostream>
#include <vector>

std::string longestCommonSubseq(std::string str1, std::string str2) {
    int m = str1.size();
    int n = str2.size();

    // 创建一个二维数组，dp[i][j]表示str1前i个字符和str2前j个字符的最长公共子序列长度
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));

    // 遍历字符串，填充dp数组
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (str1[i - 1] == str2[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数组底部回溯构建最长公共子序列
    std::string result;
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (str1[i - 1] == str2[j - 1]) {
            result = str1[i - 1] + result;
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }

    return result;
}

int main() {
    std::string str1 = "ABCDGH";
    std::string str2 = "AEDFHR";
    std::cout << "最长公共子序列: " << longestCommonSubseq(str1, str2) << std::endl;
    return 0;
}