视频讲解：https://www.bilibili.com/video/BV1ye4y1L7CQ

https://programmercarl.com/1143.%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97.html

1.本题还是求子序列，对于dp数组的定义是dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]还是因为这样可以减少初始化数组的烦恼，将初始化的操作交给递归公式进行。

本题我遇上一个题最大的疑惑如下：

• LCS：因为不要求连续，需要取「上方」或「左方」的最大值，确保问题的最优解。

• 最大重复子数组：要求连续，一旦不匹配当前状态直接归零，问题的状态转移简单，无需考虑「最大值」的逻辑。

所以本题的递归公式里的当值不相等的时候我们从左面和上面取一个最大值更新状态。

CPP

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));

        for(int i = 1; i <= text1.size(); i++){
            for(int j = 1; j <= text2.size(); 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[text1.size()][text2.size()];
    }
};