DP Solution :-)


#1
int Solution::numTrees(int n) {

long long mod = 1000000007;
    long long dp[n+1];
    
    memset(dp,0,sizeof(dp));
    
    dp[0]=1;
    dp[1]=1;
    dp[2]=2;
    
    for(int i=3;i<=n;i++)
    {
        if(i%2==0)
        {
            for(int j=0;j<i/2;j++)
            {
                dp[i]= (dp[i] + (2*(dp[j]%mod)*(dp[i-j-1]%mod))%mod)%mod;
            }
        }
        
        else
        {
            for(int j=0;j<i/2;j++)
            {
                dp[i]= (dp[i] + (2*(dp[j]%mod)*(dp[i-j-1]%mod))%mod)%mod;
            }
            
            dp[i]= (dp[i] + ((dp[i/2]%mod)*(dp[i/2]%mod))%mod)%mod;
            
            
            
        }
    }
    
    return dp[n];

}