[Java Solution] easy to understand using DP with explanation.


  • 0
    public class Solution {
    public int numTrees(int n) {
       if(n==0) return 0;
       //dp[i] means the number of unique BSTs when having i nodes.
       int[] dp=new int[n+1];
       //dp[0] mean an empty child tree
       dp[0]=1; 
       for(int i=1;i<=n;i++){
           for(int root=1;root<=i;root++){
               //choose a root node from [1...i], for each root,the number of unique BSTs is number[left]*number[right]
               //root-1 is the nodes number of its left child tree;
               //i-root is the nodes number of its right child tree;
               //sum all the dp[root], we can get dp[i]
               dp[i]+=dp[root-1]*dp[i-root];
           }
       }
       return dp[n];
    }
    

    }


Log in to reply
 

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