**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]);
}
```