163. Unique Binary Search Trees

以某个点i作为根节点时，BST的数目为i左边所有点的BST的个数 * i右边所有点的BST的个数 定义Count[i]为i个数能产生的Unique Binary Tree的数目， {} 0个Node Count[0] = 1 {1} 1个Node Count[1] = 1 {1, 2} 2个Node Count[2] = Count[0] * Count[1] + Count[1] * Count[0] {1,2,3} 3个Node Count[3] = Count[0] * Count[2] // root = 1, 2 and 3 are on the right side + Count[1] * Count[1] // root = 2, 1 is on the left, and 3 is on the right side + Count[2] * Count[0] // root = 3, 1 and 2 are on the left side

public class Solution {
    /**
     * @param n: An integer
     * @return: An integer
     */
    public int numTrees(int n) {
        // write your code here
        int[] count = new int[n+1];
        if(n <= 1){
            return 1;
        }
        count[0] = 1;
        count[1] = 1;
        for(int i = 2; i < n+1; i++){
            for(int j = 0; j < i; j++){
                count[i] += count[j] * count[i-j-1];
            }
        }
        
        return count[n];
    }