```
class Solution {
public:
int numTrees(int n) {
vector<int> vi{1,1};
for(int i=2;i<=n;++i){
int sum=0;
for(int t=0;t<i;++t){
sum+=vi[t]*vi[i-1-t];
}
vi.push_back(sum);
}
return vi[n];
}
};
```

a(n)=a0a(n-1)+……+a(n-1)a0;

you can draw tree tree to understand it. **: )**

(sorry for terrible edition)

for example n=3;

```
_ _ 3 _ 2 _ 1 ____
| 2| |1| |3| |2 |
|1_ _| | 3|
a2 * a0 a1 * a1 a0 * a2
```