Simple and Elegant DP C++ 0 ms


  • 0
    B
    int numTrees(int n) {
            
            int arr[n+1];
            
            int left = 0;
            int right = 0;
            int sum = 0;
            
            arr[0] = 1;
            arr[1] = 1;
            
            
            for(int i = 2; i <=n; i++){
                
                for(int j = 1; j <= i; j++){
                    
                    left = arr[j-1];
                    right = arr[i-j];
                    sum += left*right;
                    
                }
                
                arr[i] = sum;
                sum = 0;
            }
            
            return arr[n];
        }
    };

Log in to reply
 

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