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

Source: leetcode | Difficulty: MEDIUM
Tags: Mathematics

Tree algorithms

Dynamic programming

Range queries

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

Solutions:
class Solution:
	hash = {}

	def numTrees(self, n):
		if n == 0:
			return 1
		if n == 1 or n == 2:
			return n
		try:
			return self.hash[n]
		except KeyError:
			pass
		resSum = 0
		for i in range(n):
			tempSum = self.numTrees(i) * self.numTrees(n - (i + 1))
			resSum += tempSum
		self.hash[n] = resSum
		return resSum


class Solution:

	def numTrees(self, n):
		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):
		if n < 1:
			return 1
		tree_nums = [0] * (n + 1)
		tree_nums[0] = 1
		tree_nums[1] = 1
		for t in range(2, n + 1):
			for root in range(1, t + 1):
				lt_num = root - 1
				rt_num = t - root
				tree_nums[t] += tree_nums[lt_num] * tree_nums[rt_num]
		return tree_nums[n]


class Solution:

	def numTrees(self, n):
		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):

		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))))
			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):
		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):
		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]


class Solution:

	def numTrees(self, n):
		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):
		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):
		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):
		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):
		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:

	def numTrees(self, n):
		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]