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

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

问题描述: 给定两个字符串 s1 和 s2，找出它们的最长公共子序列 (LCS)。

动态规划法

动态规划法是一种常用的解决最优化问题的算法。我们可以使用一个二维数组 dp 来存储中间结果，其中 dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符的最长公共子序列的长度。

伪代码:

1. 初始化动态规划表 dp，将所有元素初始化为 0
2. 遍历两个字符串 s1 和 s2 的每个字符 i 和 j
3. 如果 s1[i] 等于 s2[j]，则 dp[i][j] = dp[i-1][j-1] + 1
4. 如果 s1[i] 不等于 s2[j]，则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])
5. 返回 dp[m][n]，其中 m 和 n 分别为 s1 和 s2 的长度

C++代码:

int longestCommonSubsequence(string s1, string s2) {
    int m = s1.length();
    int n = s2.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(s1[i-1] == s2[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];
}

代码解析:

• 首先，初始化一个二维数组 dp，大小为 (m+1) * (n+1)，其中 m 和 n 分别为 s1 和 s2 的长度。
• 然后，我们使用两层循环遍历 s1 和 s2 的所有字符，并根据当前字符是否相等来更新 dp 数组的值。
• 最后，dp[m][n] 即为 s1 和 s2 的最长公共子序列的长度。

示例:

假设 s1 = "abcde"，s2 = "ace"，则它们的 LCS 为 "ace"，长度为 3。

总结:

动态规划法是一种高效的求解最长公共子序列问题的算法，它利用中间结果来避免重复计算，提高了算法效率。