```
public int numTrees(int n) {
if(n<=2){
return n;
}
int[] num=new int[n+1];
num[0]=0;
num[1]=1;
num[2]=2;
for(int i=3;i<n+1;i++){
num[i]=num[i-1]*2;
for(int j=1;j<=i-1-1;j++){
num[i]+=num[j]*num[i-1-j];
}
}
return num[n];
}
```

Eg, if n=4, then we need to count num[3] * 2, because for each of the possible binary tree of n=3, we can insert 4 in 2 positions. Then we also can insert 4 "into" tree-3, i.e. break 123 into two groups

[1] 4 [23] or [12] 4 [3] (please imagine the tree structure, it doesn't violate the binary property, but just divide 123 apart into 2 parts)

for the first condition, we have num[1]*num[2] possibilities, and for the second one, we have num[2]*num[1] possibilities. Thus

num[4] = num[3] * 2 + num[1] * num[2] + num[2] * num[1]

num[5] = num[4] * 2 + num[1] * num[3] + num[2] * num[2] + num[3] * num[1]