96. Unique Binary Search Trees.java

public class BST {

	public int numTrees(int n) {
		int[] arr = new int[20];
		
		arr[0] = 1;
		arr[1] = 1;
		
		int cnt = 0;
		for (int i = 2; i <= n; i++) {
			cnt = 0;
			for (int j = 1; j <= i; j++) cnt += arr[j-1]*arr[i-j];
			arr[i] = cnt;
		}
		
		return arr[n];
	}
	public static void main(String[] args) {
		int n = 4;
		new BST().numTrees(n);
	}

}