https://leetcode.cn/problems/longest-common-subsequence/
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

大多数可以以结尾做可能性展开，讨论有多少种情况

枚举两个字符串长度分别为x和y的情况下，最长公共子序列是多长

分别讨论结尾的情况，如果结尾处两个字符串的字符相等，就dp[x][y]=max(dp[x-1],dp[y-1])+1,不然就分别讨论两边的某一边不取的情况下取最优

string s1,s2;
int dp[1010][1010];
int  dfs(int x,int y)
{
    if(x==0||y==0) return 0;
    if(dp[x][y]!=-1) return dp[x][y];

    int ans;
    if(s1[x-1]==s2[y-1]) ans=dfs(x-1,y-1)+1;
    else ans=max(dfs(x,y-1),dfs(x-1,y));
    dp[x][y]=ans;
    return ans;
}
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
         s1=text1;
         s2=text2;
        int n=s1.length();
        int m=s2.length();
        for(int i=0;i<=n;i++)
        {
            for(int j=0;j<=m;j++)
            {
                dp[i][j]=-1;
            }
        }
        dfs(n,m);
        return dp[n][m];
    }
};

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
         s1=text1;
         s2=text2;
        int n=s1.length();
        int m=s2.length();

        for(int i=0;i<=n;i++)
        {
            for(int j=0;j<=m;j++)
            {
                dp[i][j]=0;
            }
        }
        //dfs(n,m);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(s1[i-1]==s2[j-1])
                {
                    dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
                }
                else{
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[n][m];
    }
};

也可优化一维，画dp表