Unique Binary Search Trees @LeetCode

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

	package leetcode.tree;
	/**
	* Solution: DP. Count[i] means Unique BST count generated from [0, i]. Like i = 2, only two.
	*
	* Count[i] = ∑ Count[0...k] * [ k....i-1] 0<= k < i.
	* Take care of boundary. 0 means empty tree,
	*
	* 看三个元素的数组，可以发现BST的取值方式如下：
	Count[3] = Count[0]*Count[2] (1为根的情况) left 0个 node, right 2个
	+ Count[1]*Count[1] (2为根的情况) left 1个 node, right 1个
	+ Count[2]*Count[0] (3为根的情况) left 2个 node, right 0个
	*
	* Reference: http://fisherlei.blogspot.com/2013/03/leetcode-unique-binary-search-trees.html
	*
	* @author jeffwan
	* @date Apr 7, 2014
	*/
	public class UniqueBinarySearchTrees {
	public int numTrees(int n) {
	int[] count = new int[n + 1];
	count[0] = 1;
	count[1] = 1;
	for (int i = 2; i <= n; i++) {
	for (int j = 0; j < i; j++) {
	count[i] += count[j] * count[i - j - 1];
	}
	}
	return count[n];
	}
	}

view raw UniqueBinarySearchTrees.java hosted with ❤ by GitHub