Relatively fast C++ implementation


  • 0
    4
    class Solution
    {
    public:
        	int numTrees( int n )
        	{
    		        int * a =new int[n + 1];
    		        a[0] = 0;
    		        a[1] = 1;
    		        a[2] = 2;
    		        a[3] = 5;
    		
    		for( int i = 4; i <= n; ++i )
    		{
    			    int current = 2 * a[i - 1] + 2 * a[i - 2];
    
    	    		for( int j = 3; j < i - 1; ++j )
    		    	{
    			        	current += ( a[j - 1] * a[i - j] );
    			    }
    			    a[i] = current;
    		}
    	        	int out = a[n];
    	        	delete [] a;
    		        return out;
        	}
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.