UniqueBST.java

//  Unique Binary Search Trees [LEETCODE][JUNE CHALLANGE]

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

//Example:

//Input: 3
//Output: 5
//Explanation:
//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

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