Simple Java DP solution


  • 0
    class Solution {
        public int numTrees(int n) {
            
            if(n < 3) return n;
            
            int[] arr = new int[n+1];
            arr[1] = 1;
            arr[2] = 2;        
            
            for(int i=3;i<=n;++i){
                for(int j=1;j<=i;++j){
                    if(j == 1) arr[i] += arr[i-j];
                    else if(j == i) arr[i] += arr[i-1];
                    else arr[i] += arr[i-j] * arr[j-1];
                }
            }        
            
            return arr[n];
        }
    }
    

    Let me know if there are any queries or any improvements on this.


Log in to reply
 

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