题目大意：1~n的自然数，可以组成多少个不同的二叉搜索树。例子如下：
法一：卡特兰数。通项公式C(2n, n)/(n+1)=C(2n, n) - C(2n, n+1)。代码如下（耗时0ms）：
1 public int numTrees(int n) { 2 //卡特兰数 3 //C(2n, n)/(n+1) 4 long res = 1; 5 for(int i = n + 1; i <= n * 2; i++) { 6 res = res * i / (i - n); 7 } 8 return (int)(res / (n + 1)); 9 }
法二：DP。利用的也是卡特兰数。代码如下（耗时0ms）：
1 public int numTrees(int n) { 2 int[] dp = new int[n + 1]; 3 dp[0] = 1; 4 dp[1] = 1; 5 for(int i = 2; i <= n; i++) { 6 for(int j = 0; j < i; j++) { 7 dp[i] += dp[j] * dp[i - j - 1]; 8 } 9 } 10 return dp[n]; 11 }