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
思路：BST树的个数为卡特兰数，即C(2n,n)/(n+1)。这道题如果用暴力的手段，即求出2n*(2n-1)...*(n+1)会超
出数据类型的范围。其实C(n,m)=C(n-1,m-1)+C(n-1,m)，这个公式可以这样证明：假设有一堆球，球的个数为n，
现在要求从这一堆球中取出m个白球。从中任取一个球，这时有两种情况，1.这个球是白球，则需要从剩下的n-1个
球中取出m-1个白球，有C(n-1,m-1)种情况。2.这个球不是白球，则需要从剩下的n-1个球中取出m个白球，有C(n-1,m)。故公式得证。代码如下：
class Solution {
public:
int numTrees(int n) {
int res = 1;
if (n==0) {
return 0;
}
if (n==1) {
return 1;
}
int i,j;
int f[2*n+1][n+1];
for(i=0; i<=2*n; ++i) {
f[i][0] = 1;
}
for(i=0; i<=n; ++i) {
f[0][i] = 1;
}
for(i=1; i<=n; ++i) {
for(j=1; j<=2*n; ++j) {
if (i == j) {
f[j][i] = 1;
}
else {
f[j][i] = f[j-1][i-1] + f[j-1][i];
}
}
}
return f[2*n][n] / (n+1);
}
};