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

下面是使用动态规划法求解最长公共子序列问题的c++算法实现：

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

int main()
{
    string str1, str2;
    cin >> str1 >> str2;
    int len1 = str1.length(), len2 = str2.length();
    int dp[len1 + 1][len2 + 1]; // 定义dp数组
    for (int i = 0; i <= len1; i++) {
        dp[i][0] = 0;
    }
    for (int j = 0; j <= len2; j++) {
        dp[0][j] = 0;
    }
    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (str1[i - 1] == str2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1; // 相同则加1
            }
            else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); // 不同则取左、上两个状态的较大值
            }
        }
    }
    cout << dp[len1][len2] << endl; // 输出最长公共子序列长度
    return 0;
}

算法思路：

我们定义 $dp[i][j]$ 表示字符串 $str1$ 的前 $i$ 个字符和字符串 $str2$ 的前 $j$ 个字符的最长公共子序列长度。初始化时，$dp$ 数组的第一行和第一列都为 $0$，因为其中一个字符串为空字符串时，它的最长公共子序列长度一定为 $0$。接着，我们从字符串 $str1$ 的第 $1$ 个字符和字符串 $str2$ 的第 $1$ 个字符开始遍历，如果这两个字符相等，那么此时的最长公共子序列长度就应该是 $dp[i-1][j-1]+1$；如果这两个字符不相等，那么此时的最长公共子序列长度就应该是 $dp[i-1][j]$ 和 $dp[i][j-1]$ 中较大的那一个。最后，$dp[len1][len2]$ 即为所求的最长公共子序列长度。

算法复杂度：

该算法的时间复杂度为 $O(mn)$，其中 $m$ 为字符串 $str1$ 的长度，$n$ 为字符串 $str2$ 的长度。空间复杂度为 $O(mn)$。