conclusion:the number of different BST of n nodes =the number of different shapes of binary tree of n nodes

if a BST is like this:

A

...\

.....B

..../

..C

we can know the inorder traversal is A C B

if the values of this tree is 1,2,3.then A=1 C=2 B=3 definitely

so we can see:once we have decided the shape of the BST,then we can put [1,2,...,n] to this tree in just one method.

so the problem becomes how many shapes are there for n nodes?

for this problem,suppose the we have a root node,then we can assume the left subtree has x nodes(0<=x<=n-1),so the right subtree has n-x nodes

using dp[i] to represent the number of shapes for a binary tree of i nodes

dp[i]=sigma{dp[j]*dp[i-1-j] | 0<=j<=i-1} this means when we give j nodes to the left subtree,then the number of different shapes of the whole tree =the number of different shapes of the left subtree * the number of different shapes of the right subtree.and obviously,we can give 0,1,2,...,i-1 nodes to the left subtree.

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