```
public class Solution {
public int numTrees(int n) {
if (n < 3) return n;
int trees[] = new int[n + 1]; // extra space for n=0
trees[0] = 1; // we can create one empty tree with n = 0
trees[1] = 1; // we can create one tree with n = 1
trees[2] = 2; // we can create two trees with n = 2
for (int numNodes = 3; numNodes <= n; numNodes++) {
for (int nodesOnLeft = 0; nodesOnLeft < numNodes; nodesOnLeft++) {
// imagine a tree with a root, some elements on left, and remaining on right
int nodesOnRight = numNodes - nodesOnLeft - 1;
trees[numNodes] += trees[nodesOnLeft] * trees[nodesOnRight];
}
}
return trees[n];
}
}
```