My simple dp solution with explanation


  • 2
    Y
       basic idea is the recursion relationship between dps
       eg. n=4 
       1 is the root: left 0 node right 3 nodes :temp[1]=dp[0]*dp[3]=5
       2 is the root: left 1 node right 2 nodes :temp[2]=dp[1]*dp[2]=2
       3 is the root: left 2 node right 1 nodes :temp[3]=dp[2]*dp[1]=2
       4 is the root: left 3 node right 0 nodes :temp[4]=dp[3]*dp[0]=5
       dp[4]=temp[1]+...temp[4]=14
    
     public int numTrees(int n) {
        	if(n==0) return 0;
        	if(n==1) return 1;
            int[] dp=new int[n+1];
            dp[0]=1;
            dp[1]=1;//n=1
            dp[2]=2;//n=2
            for(int i=3;i<=n;i++){
            	for(int j=1;j<=i;j++){
            		dp[i]+=dp[j-1]*dp[i-j];
            	}
            }
            return dp[n];
        }

Log in to reply
 

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