最长公共子序列c++ 动态规划

以下是一个使用动态规划算法求解最长公共子序列的C++示例代码：

#include <iostream>
#include <vector>
#include <algorithm>

int longestCommonSubsequence(std::string text1, std::string text2) {
    int m = text1.length();
    int n = text2.length();
    
    std::vector<std::vector<int>> dp(m+1, std::vector<int>(n+1, 0));
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1[i-1] == text2[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 text1 = "ABCBDAB";
    std::string text2 = "BDCAB";
    
    int result = longestCommonSubsequence(text1, text2);
    
    std::cout << "Length of longest common subsequence: " << result << std::endl;
    
    return 0;
}

该代码使用了一个二维数组`dp`来保存最长公共子序列的长度。其中`dp[i][j]`表示`text1`的前`i`个字符和`text2`的前`j`个字符的最长公共子序列的长度。通过遍历`text1`和`text2`的所有字符，根据当前字符是否相等来更新`dp`数组。最后返回`dp[m][n]`即为最长公共子序列的长度。