不同的二叉搜索树(递推)

拿到这个题目，首先就定位到，这肯定是一个找规律的题目，也就可以使用递推（动态规划的解法进行解决）。
然后开始疯狂找规律，其实给的这个图简化了这个题目，不然还真的不好想。

我们可以仔细分析一下样例3 这个图，二叉搜索树的树根将其余的节点分成了左右两棵字数，那么我们可以遍历树根，每一种树根的左右子树的节点树是固定的。

那么这个题目抽象一下：一个n个节点的二叉搜索树，根节点的可能性为1 ~ n ，那么递推公式就出来了

dp[i] += dp[j -1] * dp[i - j];其中j是遍历1 ~ i；
那么这个代码就很简单了：

class Solution {
    public int numTrees(int n) {
        if( n <= 2)
           return n;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3 ; i <=n ; i ++)
        { 
             for(int j = 1; j <=i ; j++)
             {
                 dp[i] += dp[j -1] * dp[i - j];
             }
        }
        return dp[n];
    }
}

整个推理大概耗时7分钟，一遍过还算比较满意。