Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?

Example:


Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Difficulty: interview

Starter code:

class Solution:
    def numTrees(self, n: int) -> int:
        

Solutions:
class Solution:
     hash = {}
     def numTrees(self, n):
         """
         :type n: int
         :rtype: int
         """
         # return base case
         if n == 0:
             return 1
         if n == 1 or n == 2:
             return n
         
         # try fetching from hash
         try:
             return self.hash[n]
         except KeyError:
             pass
         
         # holds the sum
         resSum = 0
         
         # iterate i from 1 to n-1
         # should add up (0,4), (1,3), (2,2), (3,1), (4,0)
         for i in range(n):
             #print(i,n - (i+1))
             tempSum = self.numTrees(i) * self.numTrees(n - (i+1))
             #print(tempSum)
             resSum += tempSum
             
         # append to hash
         self.hash[n]=resSum
         return resSum

class Solution:
     def numTrees(self, n):
         """
         :type n: int
         :rtype: int
         """
         res = [0] * (n+1)
         res[0] = res[1] = 1
         for i in range(2,n+1):
             for j in range(1,i+1):
                 res[i] += res[j-1] * res[i-j]
         return res[-1]

class Solution:
     def numTrees(self, n):
         """
         :type n: int
         :rtype: int
         """
         if n<1:
             return 1
             
         tree_nums = [0]*(n+1)
         tree_nums[0] = 1
         tree_nums[1] = 1    # index start with 1
         
         for t in range(2, n+1):
             for root in range(1,t+1):
                 lt_num = root-1 # nodes num which smaller than root
                 rt_num = t-root # nodes num which larger than root
                 
                 tree_nums[t] += tree_nums[lt_num]*tree_nums[rt_num]
         
         return tree_nums[n]


class Solution:
     def numTrees(self, n):
         """
         :type n: int
         :rtype: int
         """
         dp = [0]*(n+1)
         dp[0] = dp[1] = 1
         for i in range(2, n+1):
             total = 0
             for j in range(i):
                 total += (dp[j] * dp[i-j-1])
             dp[i] = total
                 
         return dp[n] 

class Solution:
     def numTrees(self, n):
         """
         :type n: int
         :rtype: int
         """
         
         """
         The most straightforward solution would be to try all possible permutations that specify the order of input in constructing a BST and counting the different ways in which the BST results. But that would take O(n!) time and O(n) space.
         Maybe it would help to use the fact that a BST is defined recursively.
         Does the topology of a subtree affects whether the parent subtree is valid or not?
         No.
         And is it possible that we get any duplicate trees when we first designate our root and then permute its subtrees? 
         No.
         So for each node i, set i as a root and then construct/permute the left and the right subtrees. 
         The parameter we need to take care of is the list of available nodes in that subtree.
         Memoize the results, too.
         """
         
         def memoize(func):
             func.cache = cache = dict()
             def memoizer(*args):
                 key = str(args)
                 if key not in cache:
                     cache[key] = func(*args)
                 return cache[key]
             return memoizer
                 
         
         @memoize
         def count(root, lower_bound, upper_bound):
             
             if upper_bound < lower_bound:
                 return 0
             
             if lower_bound == upper_bound:
                 return 1
                 
             left_combinations = max(1, sum(count(left, lower_bound, root - 1) for left in range(lower_bound, root)))
             right_combinations = max(1, sum(count(right, root + 1, upper_bound) for right in range(root + 1, upper_bound + 1)))
             #print(root, lower_bound, upper_bound, left_combinations, right_combinations)
             return left_combinations * right_combinations
         
         return sum(count(root, 1, n) for root in range(1, n + 1))
         


class Solution:
     from functools import lru_cache
     @lru_cache(maxsize=None)
     def numTrees(self, high, low=1, depth=0):
         """
         :type n: int
         :rtype: int
         """
         return sum(self.numTrees(key - 1, low, depth + 1) * self.numTrees(high, key + 1, depth + 1) for key in range(low, high + 1)) or 1

class Solution:
     def numTrees(self, n):
         """
         :type n: int
         :rtype: int
         """
         nums = [0] * (n+1)
         nums[0] = 1
         nums[1] = 1
         
         for i in range(2, n+1):
             for j in range(i):
                 nums[i] += nums[j] * nums[i - j - 1]
         return nums[n]

class Solution:
     def numTrees(self, n):
         
         dp = [0] * (n + 1)
         
         dp[0] = 1
         
         for i in range(1, n + 1):
             for j in range(i):
                 print(j)
                 print((i - j - 1))
                 dp[i] += dp[j] * dp[i - j - 1]
         
         return dp[-1]
         """
         :type n: int
         :rtype: int
         """


class Solution:
     def numTrees(self, n):
         """
         :type n: int
         :rtype: int
         """
         a = [1]
         i = 1
         while i < n:
             tmp = [sum(a), sum(a)]
             for j in range(len(a) - 1):
                 tmp.append(tmp[j + 1] - a[j]) 
             i += 1
             a = tmp
         return sum(a)

class Solution:
     def numTrees(self, n):
         """
         :type n: int
         :rtype: int
         """
         dp = [1, 1, 2]
         if n < 3:
             return dp[n]
         for i in range(3, n + 1):
             
             dp.append(sum(dp[j - 1] * dp[i - j] for j in range(1, i + 1)))
         return dp[n]


class Solution:
     def numTrees(self, n):
         """
         :type n: int
         :rtype: int
         """
         
         dp = [0 for _ in range(n+1)]
         dp[1] = 1
         dp[0] = 1
         
         for x in range(2, n+1):
             for y in range(1, x+1): 
                 dp[x] += (dp[y - 1] * dp[x-y])
                 
         return dp[-1]


class Solution:
     def numTrees(self, n):
         """
         :type n: int
         :rtype: int
         """
         if n <= 1:
             return 1
         dp = [1 for i in range(n+1)]
         for i in range(2, n+1):
             sums = 0
             for j in range(1, i+1):
                 sums += dp[j-1] * dp[i-j]
             dp[i] = sums
         print(dp)
         return dp[-1]

class Solution:
     def numTrees(self, n):
         """
         :type n: int
         :rtype: int     
         """
         M = [0 for x in range(n)]
         M[0] = 1
         for i in range(1,n):
             for j in range(1,i):
                 M[i] += M[j-1] * M[i-j-1]
             M[i] += M[i-1] * 2
         return M[n-1]

class Solution:
     from functools import lru_cache
     @lru_cache(maxsize=None)
     def numTrees(self, high, low=1):
         """
         :type n: int
         :rtype: int
         """
         return sum(self.numTrees(key - 1, low) * self.numTrees(high, key + 1) for key in range(low, high + 1)) or 1

class Solution:
     def numTrees(self, n):
         """
         :type n: int
         :rtype: int
         """
         G = [0 for _ in range(n+1)]
         G[0] = 1
         G[1] = 1
         
         for i in range(2, n+1):
             for j in range(i+1):
                 G[i] += G[j-1]*G[i-j]
                 
         return G[-1]