DP solution in Javascript


  • 0

    Not the most elegant solution but what I did with dp

    var numTrees = function(n) {
        if (n === 1) {
            return 1; 
        }
        let memo = [1,1]; // size of n
        
        for (let i = 1; i< n; i++){
            // first iteration n = 1 
            let numNodes = i + 1;
            let result = 0;
            for (let j = 0; j < numNodes; j++){
                let numLeft = j; // number of nodes to the left 
                let numRight = numNodes - (j+1); // number of stuff to the right 
                result = result + (memo[numLeft] * memo[numRight]);
            }
            memo[i + 1] = result;
        }
        return memo[n];
    };
    

    The idea is to look at what you pick as the root and look as its left and right children's number in the memo


Log in to reply
 

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