Easy to understand top-down DP solution


  • 9
    E

    For a valid BST, there must be a node that is the root. The root can be any number between 1 and n. What if the root is k where k is in between 1 and n? It becomes obvious that 1 to k-1 should be k's left children and k+1 to n should be k's right children. Thus, a recursive formula is formulated as follows:

    number of BSTs with k being the root 
    = count of BSTs of k-1 consecutive numbers * count of BSTs of n-k consecutive numbers
    

    And since we have a total of n choices for k, total number of BSTs is thus a sum of all n choices for k.

    Code in Java:

    public int numTrees(int n) {
        return numTrees(n, new int[n]);
    }
    
    private int numTrees(int n, int[] arr) {
        if(n<=1) return 1;
        if(arr[n-1] > 0) return arr[n-1];
        
        int num = 0;
        for(int i=1; i<=n; i++) 
            num += numTrees(i-1, arr) * numTrees(n-i, arr);
    
        arr[n-1] = num; // store for reuse
        return num;
    }

  • 0
    H

    What does this condition means ?

    if(arr[n-1] > 0) return arr[n-1];


  • 0
    E

    arr is the array storing previously computed results. That is, arr[3] is the number of trees when n=3. Therefore,

    if(arr[n-1] > 0) return arr[n-1];
    

    means we simply return the stored result if it is already computed.


Log in to reply
 

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