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

动态规划法求解最长公共子序列问题的伪代码和 C++ 代码

问题描述： 给定两个字符串 text1 和 text2，求解它们的最长公共子序列 (Longest Common Subsequence, LCS) 的长度。

动态规划法：

伪代码：

初始化一个二维数组 dp，其中 dp[i][j] 表示字符串 A 的前 i 个字符和字符串 B 的前 j 个字符的最长公共子序列的长度。
对于 i=0 和 j=0，将 dp[i][j] 赋值为 0。
对于 i=1 到 n 和 j=1 到 m，进行如下操作：
- 如果字符串 A 的第 i 个字符等于字符串 B 的第 j 个字符，则 dp[i][j] = dp[i-1][j-1] + 1。
- 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
返回 dp[n][m]。

C++ 代码：

int longestCommonSubsequence(string text1, string text2) {
    int n = text1.size(), m = text2.size();
    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            if(text1[i-1] == text2[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[n][m];
}

解释：

代码中使用了二维数组 dp 来存储子问题的解。dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列的长度。
遍历所有可能的子问题，并根据当前字符是否相等来更新 dp 数组的值。
最终返回 dp[n][m]，即 text1 和 text2 的最长公共子序列长度。

示例：

text1 = 'abcde'
text2 = 'ace'
longestCommonSubsequence(text1, text2) == 3 // 最长公共子序列为 'ace'，长度为 3

总结：

动态规划法为求解最长公共子序列问题提供了一种高效的解决方案，其核心思想是将问题分解成子问题，并利用子问题的解来求解原问题。通过 C++ 代码实现，我们可以轻松地使用动态规划算法来解决这一经典问题。