# DP solution with a different explanation

• 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];
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.