class Solution {
public:
    
    int LCS(string s1, string s2) {
        if(s1.length()==0||s2.length()==0) return 0;
        int m=s1.length();
        int n=s2.length();
        vector<int> v(m,0);
        vector<vector<int>> dp(n,v);
        dp[0][0]=s1[0]==s2[0]?1:0;
        for(int j=1;j<m;j++){
            dp[0][j]=(s2[j]==s1[0])?1:dp[0][j-1];
        }
        for(int i=1;i<n;i++){
            dp[i][0]=(s1[i]==s2[0])?1:dp[i-1][0];
        }
        for(int i=1;i<n;i++){
            for(int j=1;j<m;j++){
                int p1=(s2[j]==s1[i])?1+dp[i-1][j-1]:0;
                int p2=dp[i][j-1];
                int p3=dp[i-1][j];
                dp[i][j]=max(max(p1,p2),p3);
            }
        }
        return dp[n-1][m-1];
    }
};