Solution based on dynamic programming O(n^2) instead of exponencial


  • 1
    R
    class Solution {
            
        public:
        
            int numTrees(int n) {
            
                // We use a vector to memoize subproblem's results:
                int results[n + 1];
                results[0] = 1;
                for (int i = 1; i <= n; ++i) {
                    
                    // Every iteration uses previous iterations results:
                    results[i] = numTreesRec(results, i);
                }
            
                return results[n];
            }
        
            int numTreesRec(const int* results, int n) {
                
                int res = 0;
                
                // Calculates the combinations generated when the root node is
                // one on the left half of the set:
                int hn = n / 2;
                for (int i = 0; i < n / 2; ++i) {
                
                    res += results[i] * results[n - (i + 1)];
                }
                
                // For combinations generated when the root node is  one of the
                // right half we know that is the same as the former step, hence
                // we just multiply by two:
                res *= 2;
                
                // If n is odd we need to add the combinations when the middle node is root:
                if (n & 1) {
                    
                    int i = n / 2;
                    res += results[i] * results[n - (i + 1)];
                }
        
                return res;
            }
        };

  • 11
    L
    class Solution {
    public:
        int numTrees(int n) {
            long long ans = 1;
            for(int i = 1; i <= n; ++ i)
                ans  = ans * 2 * (2 * i - 1) / (i + 1);
            return (int) ans;
        }
    }; 
    

    O(n) time, constant space base on catalan number.


  • 2
    H

    I'm not sure why your solution must be so long. There's no need to divide by 2 in the solution. This is my DP solution using C++:

    int numTrees(int n) {

    // array[i] contains the number of unique BSTs containing i nodes.
    int array [n + 1];
    array[0] = 1;
    
    for(int i = 1; i <= n ; i++) {
        array[i] = 0;
        for(int numNodes = 0; numNodes <= i - 1; numNodes++) {
            array[i] += array[numNodes] * array[i - 1 - numNodes];
        }
    }
    
    return array[n];
    

    }

    Note that my recursive solution, which ran in exponential time, was also accepted.

    int numTrees(int n) {

    if(n == 0) return 1;
    int sum = 0;
    
    for(int i = 0; i <= n - 1; i++) {
        sum += numTrees(i) * numTrees(n - 1 - i);
    }
    
    return sum;
    

    }


  • 0
    S

    Thanks for your post. But, have you ever noticed this words Writing code? Select a code block and click on the {} button to preserve code formatting. above your text editor?


  • 0
    H

    I clicked that, and that's how it formatted my code =( Not sure why actually.


  • 0
    S

    Select entire code then click it.


  • 0
    L

    what's the idea behind your solution? why does array[numNodes] * array[i - 1 - numNodes]; what's that mean?


  • 0
    H

    Since the number of node configurations in the left subtree, LEFT, is independent of the number of node configurations in the right subtree, RIGHT, the total number of node configurations in a given tree with k nodes in the left subtree and (n - 1 - k) nodes in the right subtree is given by LEFT * RIGHT.

    This is why you take the product of those two array values.


  • 0
    H

    One could only produce this solution if they solved the recursive formula. Otherwise, in most interview situations, you wouldn't have enough time to perform the mathematics behind this.

    That being said, it's cool if you find the constant space solution. Maybe an interviewer would appreciate this solution more than a DP solution?


  • 4
    R

    My idea is similar to yours, but maybe its more clear to understand. We use DP to store total number of unique BST for each n. When calculate that, we separate the array (1...n) by choosing roots from 1 to n, then we can multiply left situation by right situation, and sum them up.
    Here is the code:

    //using DP to avoid duplicate calculate
    class Solution {
    public:
    	int numTrees(int n) {
    		unordered_map<int, int> hashmap;
    		hashmap[0] = 1;
    		hashmap[1] = 1; //store total number of unique BST for n
    		if(n == 0 || n == 1) {
    			return n;
    		}
    		for(int i = 2; i <= n; ++i) {
    			//calculate unique BST when there is i numbers
    			int total = 0;
    			for(int j = 1; j <= i; ++j) {
    				//calculate uniques BST when j is root
    				total += (hashmap[j - 1] * hashmap[i - j]); //multiply left and right
    			}
    			hashmap[i] = total;
    		}
    		return hashmap[n];
    	}
    };  

  • 2
    Z
    class Solution:
        # @return an integer
        def numTrees(self, n):
            Num=[1,1]+[0]*n;
            for i in range(2,n+1):
                for j in range(n):
                    Num[i]+=Num[j]*Num[n-j-1];
            return Num[n];
    

    my accepted python code.


  • 0
    R

    An hashmap with hash function hash(n) { return n } with max n known at the beginning, implodes into a vector<int>. But since N is known if your compile support C99 or C++11 you can just use a simple vector int vect[n] that is even faster because everything is in the stack. Faster than mine because you don'thave the overhead of the recursive calls.
    You can replace it to obtain a litle performance improvement.


  • 0
    N

    Why there is ";" at the end of sentence...


  • 0
    Z

    Because I am a C/C++ programmer, and I learn Python at part-time and I am used to the C++ coding style.


  • 0
    J

    My code is the same with you, but you provided a different view, and very easy to understand. Thx.


  • 0

    Thank you so much for the explanation you wrote before your code. Many take them for obvious but for someone who first time solve this problem, really understanding the logic of the recursion is the key point.


  • 0
    F

    The other solution only give the code, but did not tell the original logic. Only your code gave us the the most basic logic. Thx!


  • 0
    R

    Great explanation! Thank you very much.


Log in to reply
 

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