This solution is similar to another top answer but with a different explanation which is based on the number of nodes on each subtrees.

{Number of trees with n nodes} = {number of trees with 0 on left and n - 1 on right} + {number of trees with 1 on left and n - 2 on right} + ... + {number of trees with n - 1 on left and 0 on right}

As total of nodes is n, putting i on left, 1 on root, then the right will be n - 1 - i.

Therefore: f(n) = f(i) * f(n - 1 - i) for i = 0 to n - 1, where f(n) is the number of trees with n nodes. Number of trees with 0 nodes is 1

```
int numTrees(int n) {
vector<int> num_trees(n+1);
num_trees[0] = 1;
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= i - 1; ++j)
num_trees[i] += num_trees[j] * num_trees[i - 1 - j];
return num_trees.back();
}
```