Top-down approach (memoization) solution


#1

public class Solution {
public int dp[];

public int numTrees(int A) {
    dp = new int[A + 1];
    Arrays.fill(dp, -1);
    return f(A);
}

public int f(int n) {
    if (n == 0)
        return 1;
    
    if (n == 1)
        return 1;
        
    if (n == 2)
        return 2;
    
    if (dp[n] != -1)
        return dp[n];
        
    int ans = 0;
    
    for (int i = 1; i <= n; i++) {
        // root is i
        ans += f(i - 1) * f(n - i);
    }
    
    dp[n] = ans;
    
    return ans;
}

}