96.js

/** ------------------------------------------------------------------------------
 * 
 * 96. Unique Binary Search Trees
 * Topics: Binary Tree
 * https://leetcode.com/problems/unique-binary-search-trees/description/
 * 
 ------------------------------------------------------------------------------ */
/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function (n) {
  let memo = new Array(n + 1).fill(0)
  memo[0] = 1
  memo[1] = 1
  for (let i = 2; i <= n; i++) {
    for (let j = 1; j <= i; j++) {
      G[i] += G[j - 1] * G[i - j]
    }
  }
  return G[n]
}

var numTrees = function (n) {
  const cache = []
  return numTreeMemo(n, cache)
}

var numTreeMemo = (n, cache) => {
  if (n == 1) return 1
  if (cache[n]) return cache[n]

  let totalTrees = 0

  for (let root = 1; root <= n; root++) {
    let leftTrees = 1

    if (root > 1) leftTrees = numTreeMemo(root - 1, cache)

    let rightTress = 1

    if (root < n) rightTress = numTreeMemo(n - root, cache)

    totalTrees += leftTrees * rightTress
  }
  cache[n] = totalTrees
  return totalTrees
}

console.log()