Top down approach very easy


#1

int t[1001][1001];

int recur(string a, string b, int n, int m){
if(n < 0 || m < 0)
return 0;

if(t[n][m] != -1)
    return t[n][m];
    
if(a[n] == b[m])
    return t[n][m] = 1 + recur(a, b, n-1, m-1);

else{
   return t[n][m] = max(recur(a, b, n-1, m), recur(a, b, n, m-1)); 
}

}

int Solution::solve(string a, string b) {
memset(t, -1, sizeof(t));
return recur(a, b, a.length()-1, b.length()-1);
}