c++计算最长公共子序列的长度的动态算法

在C++中，计算两个字符串的最长公共子序列（Longest Common Subsequence, LCS）通常使用动态规划（Dynamic Programming）方法。这个过程涉及到创建一个二维数组，数组的行代表第一个字符串的每个字符，列代表第二个字符串的每个字符。对于数组中的每个元素 `(i, j)`，其值表示前缀字符串 `str1[0:i]` 和 `str2[0:j]` 的最长公共子序列的长度。

算法步骤如下：

1. 初始化一个二维数组 `dp`，其中 `dp[i][j]` 表示字符串 `str1[0:i]` 和 `str2[0:j]` 的LCS长度。
2. 遍历矩阵，如果 `str1[i-1] == str2[j-1]`，说明当前字符在两个串中都是LCS的一部分，那么 `dp[i][j] = dp[i-1][j-1] + 1`。
3. 否则，如果 `str1[i-1] != str2[j-1]`，取两相邻单元格的最大值作为当前值，即 `dp[i][j] = max(dp[i-1][j], dp[i][j-1])`，因为在这种情况下，要么跳过第一个字符串的一个字符，要么跳过第二个字符串的一个字符，LCS不会变长。
4. 最终，`dp[str1.length()][str2.length()]` 就是两个字符串的最长公共子序列长度。

以下是简单的伪代码形式：

int lcsLength(string str1, string str2) {
    int len1 = str1.length();
    int len2 = str2.length();

    int dp[len1+1][len2+1];

    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;
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }

    return dp[len1][len2];
}