最长公共子序列问题C++代码实现

以下是最长公共子序列问题的 C++ 代码实现：

#include <iostream>
#include <cstring>
using namespace std;

int LCS(string str1, string str2, int m, int n) {
    int dp[m + 1][n + 1];

    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            }
            else 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]);
            }
        }
    }

    return dp[m][n];
}

int main() {
    string str1 = "AGGTAB";
    string str2 = "GXTXAYB";

    int m = str1.size();
    int n = str2.size();

    cout << "Length of LCS: " << LCS(str1, str2, m, n) << endl;

    return 0;
}

在这个实现中，我们定义一个二维数组 `dp` 来存储最长公共子序列的长度。我们使用动态规划来解决问题。对于每个字符 `str1[i-1]` 和 `str2[j-1]`，我们可以有两种选择：

1. 如果它们相等，则它们一定属于最长公共子序列，因此我们将它们添加到最长公共子序列中，并将长度加一。此时，我们需要在 `str1[0:i-2]` 和 `str2[0:j-2]` 中找到最长公共子序列。
2. 如果它们不相等，则它们不能同时出现在最长公共子序列中。这意味着我们需要找到 `str1[0:i-2]` 和 `str2[0:j-1]` 或 `str1[0:i-1]` 和 `str2[0:j-2]` 中的最长公共子序列。

我们使用 `dp[i][j]` 存储 `str1[0:i-1]` 和 `str2[0:j-1]` 的最长公共子序列的长度。我们可以通过填充 `dp` 数组来计算最长公共子序列的长度。具体来说，对于任意 `i` 和 `j`，如果 `str1[i-1]` 和 `str2[j-1]` 相等，则 `dp[i][j]` 等于 `dp[i-1][j-1] + 1`，否则 `dp[i][j]` 等于 `max(dp[i-1][j], dp[i][j-1])`。最终，我们将返回 `dp[m][n]`，其中 `m` 和 `n` 是 `str1` 和 `str2` 的长度。