Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example,
Given n = 3, there are a total of 5 unique BST's.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
注意：二分查找树的定义是，左子树节点均小于root，右子树节点均大于root！不要想当然地将某个点作为root时，认为其他所有节点都能全部放在left/right中，除非这个点是 min 或者 max 的。
分析：本题其实关键是递推过程的分析，n个点中每个点都可以作为root，当 i 作为root时，小于 i 的点都只能放在其左子树中，大于 i 的点只能放在右子树中，此时只需求出左、右子树各有多少种，二者相乘即为以 i 作为root时BST的总数。
开始时，我尝试用递归实现，但是超时了，可见系统对运行时间有要求。因为递归过程中存在大量的重复计算，从n一层层往下递归，故考虑类似于动态规划的思想，让底层的计算结果能够被重复利用，故用一个数组存储中间计算结果（即 1~n-1 对应的BST数目），这样只需双层循环即可，代码如下：
class Solution {
public:
int numTrees(int n) {
vector<int> num;
num.push_back(1); //在容器尾端插入一项数据，设置num[0]=1
for(int i=1; i<=n; i++){
num.push_back(0); //每次先将num[i]设置为0
if(i<3)
num[i]=i; //易知num[1]=1,num[2]=2
else{
for(int j=1; j<=i; j++)
num[i]+=num[j-1]*num[i-j]; //j为root节点，其左子树种数为j-1，右子树种数为i-j
}
}
return num[n];
}
};
其他解法：
1、1ms in C++ By Using Theorem From Graph Theory
This is my code. I use the property that the number of unique binary trees or n vertex is
{(2n)(2n-1)(2n-2)....(n+2)}/{(n)(n-1)....(2)(1)}
class Solution {
public:
int numTrees(int n) {
long long result = 1;
long long temp = 1;
for(int i = 2*n; i > n; i--){
result *= i;
temp *= (i-n);
if (result % temp == 0){
result /= temp;
temp = 1;
}
}
return result/(n+1);
}
};
2、2ms c++ using dp（动态规划）
class Solution {
public:
int numTrees(int n){
int arr[n+1][n+1];
memset(arr,0,sizeof(arr));
for(int len=1; len<=n; len++){
for(int j=1; j<=n-len+1; j++){
if(len == 1) arr[len][j] = 1;
else{
arr[len][j] += arr[len-1][j+1];
arr[len][j] += arr[len-1][j];
for(int k=1;k<len;k++) arr[len][j] += (arr[k][j]*arr[len-k-1][j+k+1]);
}
}
}
return arr[n][1];
}
};
3、
class Solution {
public:
int numTrees(int n) {
if(n==0) return 0;
int s[n+1];
int r;
s[0] = 1;
for(int i=1; i<n+1; i++)
{
s[i] = 0;
for(int l=0; l<i; l++)
{
r = i-1-l;
s[i] = s[i]+s[l]*s[r];
}
}
return s[n];
}
};