class Solution { public int numTrees(int n) { /* basically a question of catalan number , learn the first 5 catalan numbers to be able to find the pattern in questions */ int[] dp = new int[n+1]; dp[0] = 1 ; dp[1] = 1; for(int k = 2 ; k <= n ; k++){ for(int i = 0 , j = k-1 ; i<=k-1 ; i++ , j--) dp[k] += dp[i] * dp[j]; } return dp[n]; } }