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

动态规划法实现最长公共子序列是一种常见的算法，它可以用来解决两个序列之间的最长公共子序列问题。具体实现过程如下：
1. 定义一个二维数组dp，其中dp[i][j]表示序列1的前i个元素和序列2的前j个元素的最长公共子序列的长度。
2. 初始化dp数组，将dp[j]和dp[i]都设为0。
3. 遍历序列1和序列2，如果当前元素相同，则dp[i][j] = dp[i-1][j-1] + 1；否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
4. 最终dp[m][n]即为序列1和序列2的最长公共子序列的长度。

以下是C++代码实现：

int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size(), n = text2.size();
    vector<vector<int>> dp(m+1, 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] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    return dp[m][n];
}