仅供自己学习

思路：

因为这是求公共子序列，不是公共子字串，所以公共的元素可以不连续，那么暴力为每个字符找相同的字符就需要O(n^2)的时间。
考虑用两个string的长度做二维矩阵，用动态规划。定义dp[i][j]为text1长度为i，text2长度为j是的公共子序列长度，text[0:i]定义为 该text从0到i的长度。
那么可知dp[0][j]和dp[i][0]都初始化为0，因为0长度肯定和其他任意长度的text没有公共子序列。所以我们遍历要从i=1，j=1开始。
然后是状态转移方程的定义， 首先条件分为两种，第一种：text1[0:i]最后一个字符等于text2[0:j]的最后一个字符，就相当于正好找到了一个相同的字符，那么自然dp[i][j]=dp[i-1][j-1]+1，例如：'ABC'和'AC'，最后一个字符相同，而上一次的子序列长度为0，那么现在就是0+1=1；第二种：text1[0：i]最后一个字符不等于text2[0：j]的最后一个字符，相当于没有找到相同字符，那么dp[i][j]还等于上一次找的最大公共子序列长度，dp[i][j]=max(dp[i-1][j]，dp[i][j-1])，例如：'ABC'和'EBD'，那么最后一个不相等，ABC和EB，的子序列长为1，AB和EBD长为1，那么取max，就是dp[i][j]的长度1。因为我们会遍历到矩阵的每个位置，所以上述的方法同样满足一个数与其余所有数相比的过程，只是这个过程简化了只比最后一个字符，并通过前面得到的长度更新此位置得到的最长子序列,也突出的动态规划查表的概念。

代码：

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n1=text1.length(),n2=text2.length();
        vector<vector<int>> dp(n1+1,vector<int> (n2+1,0));
        for(int i=1;i<=n1;i++){
            for(int j=1;j<=n2;++j){
                if(text1[i-1]==text2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                else if(text1[i-1]!=text2[j-1]){
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[n1][n2];
    }
};