Simplest solution using catalan numbers.oms


  • 0
    S

    class Solution {
    public:
    int numTrees(int n)
    {
    long int y= catalandp(n);
    return y;
    }

    unsigned long int catalandp(unsigned int n)
        {
    
            unsigned long int catalan[n+1];
            
            catalan[0] = catalan[1] = 1;
    
            for (int i=2; i<=n; i++)
                    {
                        catalan[i] = 0;
                        for (int j=0; j<i; j++)
                        catalan[i] += catalan[j] * catalan[i-j-1];
                    }
    
    
    return catalan[n];
    

    }

    };


Log in to reply
 

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