https://leetcode.com/problems/unique-binary-search-trees/

uniqueBinarySearchTrees.js

/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function(n) {
    const memo = new Array(n+1).fill(0).map(() => new Array(n+1).fill(-1));
    
    const count = (l, r) => {
        if(r <= l) return 1;
        if(memo[l][r] !== -1) return memo[l][r];
        
        let result = 0;
        for(let i=l; i<=r; i++){ // for each val, lock it as the root
            const leftTrees = count(l, i-1); // then count the number on the left
            const rightTrees = count(i+1, r); // and the number on the right
            result += (leftTrees * rightTrees); // multiply them together
        }
        return memo[l][r] = result;
    };
    
    return count(1, n);
};