C++ 动态规划求解最长公共子序列 (LCS) 问题

本文将介绍使用动态规划算法求解最长公共子序列 (LCS) 问题的 C++ 代码实现。

伪代码

定义函数 LCS(str1, str2) 返回两个字符串的最长公共子序列长度。
初始化一个二维数组 dp，大小为 (len(str1) + 1) * (len(str2) + 1)，其中 dp[i][j] 表示 str1 的前 i 个字符和 str2 的前 j 个字符的最长公共子序列长度。
对于 i 从 0 到 len(str1)，j 从 0 到 len(str2)，执行以下步骤： a. 如果 i 或 j 等于 0，则 dp[i][j] 为 0。 b. 如果 str1[i-1] 等于 str2[j-1]，则 dp[i][j] 等于 dp[i-1][j-1] + 1。 c. 如果 str1[i-1] 不等于 str2[j-1]，则 dp[i][j] 等于 max(dp[i-1][j], dp[i][j-1])。
返回 dp[len(str1)][len(str2)]。

C++ 代码

int LCS(string str1, string str2) {
    int m = str1.length();
    int n = str2.length();
    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];
}

解释：

代码首先定义了一个函数 LCS，接受两个字符串 str1 和 str2 作为输入，并返回它们的 LCS 长度。
接着，代码初始化了一个二维数组 dp，用于存储中间结果。dp[i][j] 表示 str1 的前 i 个字符和 str2 的前 j 个字符的 LCS 长度。
然后，代码使用两层循环遍历 dp 数组，计算每个位置的值。
- 当 i 或 j 为 0 时，表示一个字符串为空，此时 LCS 长度为 0。
- 当 str1[i-1] 等于 str2[j-1] 时，表示两个字符串的当前字符相同，此时 LCS 长度等于 dp[i-1][j-1] 加 1。
- 当 str1[i-1] 不等于 str2[j-1] 时，表示两个字符串的当前字符不同，此时 LCS 长度等于 dp[i-1][j] 和 dp[i][j-1] 中的较大值。
最后，代码返回 dp[m][n]，即 str1 和 str2 的 LCS 长度。

使用示例：

string str1 = "abcde";
string str2 = "ace";
int lcs_length = LCS(str1, str2);
cout << "最长公共子序列长度为：" << lcs_length << endl; // 输出：3

总结：

本文介绍了使用动态规划算法求解最长公共子序列 (LCS) 问题的 C++ 代码实现。动态规划算法是一种高效的解决这类问题的通用方法。通过理解动态规划的思路和代码实现，你可以将它应用到其他类似问题中。