题目
思路1：
假设输入为n，输出为f(n)，则选择任意一个数字作为根节点，设左侧节点数为left，右侧节点数为right，那么可组成的二叉搜索树的数量就等于f(left)f(right)，同时当left和right互换时得到的结果相等，即：假如输入为5，那么以1为根节点时，f1(5)=f(0)+f(4),即左侧有0个节点，右侧有4个节点，同样的以5为根节点时f5(5)=f(4)+f(0)=f1(5)，因此f(5)=f1(5)2+f2(5)2+f3(5)；如果输入是偶数，比如6，那么f(6)=f1(6)2+f2(6)2+f3(6)2，（区别在于最后一项是否乘2），基于此思路可以写出如下代码：
private Map<Integer,Integer> map=new HashMap<Integer,Integer>(); //用来记录已算过的数避免重复计算
public int numTrees(int n) {
return core(1,n);
}
private int core(int lo,int hi){
int len=hi-lo+1;
if(len<3)return len;
else{
if(map.get(len)!=null)return map.get(len);
int sum=0;
for(int i=1;i<(len>>1);i++){
sum+=(core(0,i-1)*core(i+1,len-1))<<1;
}
sum+=core(lo,hi-1)<<1;
if((len&1)==1){
int mid=len>>1;
sum+=core(0,mid-1)*core(mid+1,len-1);
}
map.put(len, sum);
return sum;
}
}
思路2：
因为f(n)只依赖于f(0)-f(n-1)，因此可以用一个一维数组来依次计算f(1),f(2),f(3).....f(n-1),f(n)，计算方法和思路一相同，代码如下：
public int numTrees(int n) {
if(n<3)return n;
int[] dp=new int[n+1];
dp[0]=1;
dp[1]=1;
for(int i=2;i<=n;i++){
int mid=i>>1;
for(int j=0;j<mid;j++){
dp[i]+=dp[j]*dp[i-j-1]*2;
}
if((i&1)==1){
dp[i]+=(dp[mid]*dp[mid]);
}
}
return dp[n];
}
分析：
相比之下方法一更容易想到但是复杂度比第二种方法高，其实两种方法很类似，只是第二种方法存记录的方式使他的读取代价更低（因为采用了定长数组，相比之下HashMap的查找速度肯定是要低于数组的，而且还可能要resize），其实二者的时间复杂度都是O(n^2)，空间复杂度都是O(n)；
