```
int num[1000];
int go(int begin , int end){
if (begin >= end) return 1;
if (num[end - begin + 1]) return num[end - begin + 1];
int tmp = 0;
for (int i = begin;i <= end;i++){
tmp += (go(i + 1 , end) * go(begin , i - 1)); //multiply
}
return num[end - begin + 1] = tmp;
}
int numTrees(int n) {
memset(num , 0 ,sizeof(num));
return go(1 , n);
}
```