Find the number of different Binary Search Trees generated from 1-n.

Solution:

以某个点i作为根节点时，BST的数目为i左边所有点的BST的个数 * i右边所有点的BST的个数
count[i]为i个数能产生的Unique Binary Tree的数目

Count[3] = Count[0]_Count[2] (1为根，左边0个数，右边2个数)

• Count[1]_Count[1] (2为根，左边1个数，右边1个数)
• Count[2]*Count[0] (3为根，左边2个数，右边0个数)

Count[n+1] = ∑ Count[i] * [ n-i]

注意初始化count[0] = 1

  public int numOfTrees(int n) {
    int[] count = new int[n + 1];
    count[0] = 1;
    for (int i = 1; i <= n; i++) {
      for (int j = 0; j < i; j++) {
        count[i] += count[j] * count[i - 1 - j];
      }
    }
    return count[n];
  }