Given two strings, find the longest common subsequence (LCS).

Your code should return the length of LCS.

Example
For "ABCD" and "EDCA", the LCS is "A" (or "D", "C"), return 1.

For "ABCD" and "EACB", the LCS is "AC", return 2.

#include <iostream>
#include <vector>
#pragma GCC diagnostic error "-std=c++11"

using namespace std;

class Solution{
public:
    int subsequence(string &m,string &n){
        
        return tryString(m,n,m.size()-1,n.size()-1);
    }
private:
    int tryString(string &m,string &n,int i,int j){
        if(i==-1 || j==-1){
            return 0;
        }
        if(m[i]==n[j]){
            return 1+max(tryString(m,n,i-1,j),tryString(m,n,i,j-1));
        } else{
            return max(tryString(m,n,i-1,j),tryString(m,n,i,j-1));
        }
    }       
};

int main(){
    string m="abc";
    string n="abdc";
    cout<<Solution().subsequence(m,n)<<endl;
    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    /**
     * @param A, B: Two strings.
     * @return: The length of longest common subsequence of A and B.
     */
    int longestCommonSubsequence(string &A, string &B) {
        int az=A.size();
        int bz=B.size();
        if(az==0 || bz==0){
            return 0;
        }

        //init dp

        vector<vector<int>> dp(az+1,vector<int>(bz+1,0));
        //dp[1][1]=(A[1]==B[1] ? 1:0);

        for(int i=1;i<=az;i++){
            for(int j=1;j<=bz;j++){
                //string begin 0
                if(A[i-1]==B[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[az][bz];

    }
};

int main(){
    string A="ACBDEA";
    string B="ABCDA";

    cout<<Solution().longestCommonSubsequence(A,B);
    return 0;
}