Java top down solution


#1

public class Solution {

public int solve(String a, String b) {
    int dp[][] = new int[a.length()+1][b.length()+1];
    return recur(a, b, a.length()-1, b.length()-1, dp);
}

public int recur(String a, String b, int n, int m, int[][] dp){
    if(n < 0 || m < 0)
        return 0;
    
    if(dp[n][m] != 0)
        return dp[n][m];
        
    if(a.charAt(n) == b.charAt(m))
        return dp[n][m] = 1 + recur(a, b, n-1, m-1, dp);
    
    else{
       return dp[n][m] = Math.max(recur(a, b, n-1, m, dp), recur(a, b, n, m-1, dp)); 
    }
}

}