Unique Binary Search

	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
	/*
	"After carefully obsearve, you can find this quesiton should be solved by dp,"
	"then we create a array int[] count represent 1->n"
	"if n==0, then count[0] represent a null tree so count[0] is 1, if n=1, then only one root is possible is, so count[1]=1"
	"if n=2, then from 1->2, there should be two node, then two node could be 1root, 1 right or 1 left 1 root, so count[2]=2 "
	"Depend on this rule we can got count[3]= 0 left node*2 rigth node+2 left node * 0 right node"
	"so is n==3, so to represent 1->n, we should have three node, one root, one left, one right or two left zero right or two right"
	"zero left, the count[3]=count[0]*count[2]+count[2]*count[0]+count[1]*count[1]"
	"depndont count[3]=count[0]*count[2]+count[2]*count[0]+count[1]*count[1], we can know the rule in below code"
	*/
	public class UniqueBinarySearchTree {
	public int numTrees(int n) {
	// Start typing your Java solution below
	// DO NOT write main() function
	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];
	}
	}
	// Another two Solution
	public int numTrees(int n){
	if (n<0){
	return 0;
	}
	int[] nums=new int[n+1];
	return numTrees(n, nums);
	}
	// recursive + catch
	private int numTrees(int n, int[] nums){
	if (nums[n]!=0){
	return nums[n];
	}
	if (n<=1){
	nums[0]=1;
	nums[1]=1;
	return 1;
	}
	if (n==2){
	nums[2]=2;
	return 2;
	}
	int sum=0;
	for (int i=1; i<=n; i++){
	sum+=numTrees(i-1, nums) * numTrees(n-i, nums);
	}
	nums[n]=sum;
	return nums[n];
	}
	// pure recursive
	public int numTrees(int n) {
	if (n<1){
	return 1;
	}
	if (n==1){
	return 1;
	}
	if (n==2){
	return 2;
	}
	int sum=0;
	for (int i=1; i<=n;i++){
	sum+=numTrees(i-1) * numTrees(n-i);
	}
	return sum;
	}

view raw UniqueBinarySearchTree.java hosted with ❤ by GitHub