Lang: C++; Complexity[Time, Space]: [O(n*n), O(n)]


#1

Idea: Consider the case for integer n+1 when we already know the answer for all the integers in range [1,n]. Try to make every node as root, one by one. Soon you’ll see that whenever j is root it’s left subtree has j-1 nodes and it’s right subtree has n+1-j nodes. Such that the total arrangements possible for trees with j as root is f(j-1) * f(n+1-j), where j belongs in [1,n+1] and f: int->int is the required function.

int Solution::numTrees(int A) 
{
    vector<int> dp(A+1,0);
    dp[0]=dp[1]=1;
    for(int n=2; n<=A; n++)
    {
        for(int j=0;  j<=(n-1)/2; j++)
            dp[n] += 2*dp[j]*dp[n-j-1];
            
        dp[n] -= ((n%2)*dp[n/2]*dp[n/2]);
    }
    return ((A<2) ? A : dp[A]);
}