Leetcode96 different binary search trees

leetcode96: Different binary search trees

Title Description

Give you an integer n , Seek just by n Composed of nodes with node values from 1 To n Different from each other Binary search tree How many kinds? ？ Returns the number of binary search trees satisfying the meaning of the question .

I/o sample

 Input ：n = 3
 Output ：5

 Input ：n = 1
 Output ：1

Algorithm one ： Use dynamic programming

    // Definition of binary search tree ： If its left subtree is not empty , Then the value of all nodes on the left subtree is less than its root node , If his right subtree is not empty , Then the value of all nodes on the right subtree is greater than the value of its root node 
   // Its left and right subtrees are also binary search trees  
    int numTrees(int n)
    {
    
        // Build dynamic programming array 
        vector<int>dp(n+1,0);
        // Set initial conditions 
        dp[0]=1;
        dp[1]=1;
        // Set the equation of conversion 
        for(int i=2;i<=n;i++)
        {
    
            for(int j=1;j<=i;j++)
            {
    
                dp[i]+=dp[j-1]*dp[i-j];
            }
        }
        return dp[n];
    }

Algorithm 2 ： Use the definition of the grand number

// Kataran number 
    int numTrees2(int n)
    {
    
        long long c=1;
        for(int i=0;i<n;i++)
        {
    
            c=c*2*(2*i+1)/(i+2);
        }
        return (int)c;
    }