求解最长公共子序列的长度问题 用c++语言

求解最长公共子序列 (Longest Common Subsequence, LCS) 的长度问题是计算机科学中的经典动态规划问题。你可以使用动态规划算法来解决这个问题，尤其适用于字符串问题。在 C++ 中，可以使用二维数组 `dp` 来存储子问题的解。以下是基本的步骤：

1. 定义一个二维数组 `dp[m+1][n+1]`，其中 `m` 和 `n` 分别是两个输入字符串的长度。

2. 初始化 `dp[0][i] = dp[i][0] = 0`，因为当一个字符串为空时，它们的LCS长度为0。

3. 使用嵌套循环遍历两个字符串：
- 如果当前字符相等（str1[i] == str2[j]），则 `dp[i+1][j+1] = dp[i][j] + 1`，表示这两个字符都在LCS里，所以长度加一。
- 如果不相等，则取之前两个位置的最大值，即 `dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])`，意味着不包含其中一个字符也能构成LCS。

4. 最终结果就在 `dp[m][n]` 中，这是两个完整字符串的LCS长度。

C++ 代码示例（采用滚动数组优化空间）：

#include <iostream>
int lcsLength(std::string str1, std::string str2)
{
    int m = str1.length();
    int n = str2.length();
    int dp[m + 1][n + 1];

    // 填充dp表
    for(int i = 1; i <= m; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(str1[i - 1] == str2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    return dp[m][n];
}

int main()
{
    std::string str1 = "ABCDGH";
    std::string str2 = "AEDFHR";
    int length = lcsLength(str1, str2);
    std::cout << "Length of LCS is: " << length << std::endl;

    return 0;
}