Simple solution with easy explaination


  • 28
    A

    WE can know that by zero we can have 1 bst of null
    by 1 we have 1 bst of 1
    and for 2 we can arrange using two ways
    Now idea is simple for rest numbers. for n=3 make 1 as root node so there will be 0 nodes in left subtree and 2 nodes in right subtree. we know the solution for 2 nodes that they can be used to make 2 bsts.
    Now making 2 as the root node , there will be 1 in left subtree and 1 node in right subtree. ! node results in 1 way for making a BST.
    Now making 3 as root node. There will be 2 nodes in left subtree and 0 nodes in right subtree. We know 2 will give 2 BST and zero will give 1 BST.
    Totalling the result of all the 3 nodes as root will give 5. Same process can be applied for more numbers.

        public int number(int n){
    	if(n==0)return 1;
    		if(n==1)return 1;
    		
    		int result[]=new int [n+1];
    		result[0]=1;
    		result[1]=1;
    		result[2]=2;
    		if(n<3){
    			return result[n];
    		}
    		
    		for(int i=3;i<=n;i++){
    			for(int k=1;k<=i;k++){
    
    				result[i]=result[i]+result[k-1]*result[i-k];
    			}
    		}
    		
    		
    		return result[n];
    	}

  • 0
    H

    result [1] and result[2] can be also included into the for loop, they both fit the rules you found. But you can also leave them as now just to make the dynamic formula more clear.


  • 0
    Y

    I am confused that when n=3
    n=3, result[3]=result[3]+5
    How can I get the value of result[3]???


  • 2
    M

    @yun28 result[3] will initially be 0 and will get cumulatively added in successive iterations of k


  • 0
    G

    @mani89 It hadn't click on me until I read your answer. Thank you!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.