Given an integer. Find how many structurally unique binary search trees are there that stores the values from 1 to that integer (inclusive). 
Example 1:
Input:
N = 2
Output: 2
Explanation:for N = 2, there are 2 unique
BSTs
     1               2  
      \            /
       2         1
Example 2:
Input:
N = 3
Output: 5
Explanation: for N = 3, there are 5
possible BSTs
  1           3     3       2     1
    \        /     /      /  \     \
     3      2     1      1    3     2
    /      /       \                 \
   2      1         2                 3
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function numTrees() which takes the integer N as input and returns the total number of Binary Search Trees possible with keys [1.....N] inclusive. Since the answer can be very large, return the answer modulo 1e9 + 7.
Expected Time Complexity: O(N^{2}).
Expected Auxiliary Space: O(N).
Constraints:
1<=N<=1000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Range queries

Starter code: #User function Template for python3



class Solution:

    #Function to return the total number of possible unique BST.

    def numTrees(self,N):

        # code here

Solutions:
class Solution:

	def numTrees(self, N):
		dp = [0] * (N + 1)
		dp[0] = 1
		dp[1] = 1
		MOD = 10 ** 9 + 7
		for i in range(2, N + 1):
			count = 0
			for j in range(1, i + 1):
				leftBST = dp[j - 1]
				rightBST = dp[i - j]
				count += leftBST * rightBST
			dp[i] = count % MOD
		return dp[-1]


class Solution:

	def fact(self, n):
		k = 1
		for i in range(1, n + 1):
			k *= i
		return k

	def numTrees(self, n):
		k = self.fact(2 * n) // (self.fact(n) * self.fact(n + 1))
		return k % 1000000007


mod = 10 ** 9 + 7

class Solution:

	def Factorial(self, n, memory):
		if n <= 1:
			return n
		if memory[n] == -1:
			memory[n] = self.Factorial(n - 1, memory) * n
		return memory[n]

	def Solve(self, n):
		if n <= 2:
			return n
		memory = [-1 for i in range(2 * n + 1)]
		ans = self.Factorial(2 * n, memory) // (self.Factorial(n, memory) * self.Factorial(n + 1, memory)) % mod
		return ans

	def Tab(self, n):
		memory = [0 for i in range(2 * n + 1)]
		(memory[0], memory[1], memory[2]) = (1, 1, 2)
		for i in range(3, 2 * n + 1):
			memory[i] = i * memory[i - 1]
		return memory[2 * n] // (memory[n] * memory[n + 1]) % mod

	def numTrees(self, N):
		return self.Tab(N)


class Solution:

	def numTrees(self, n):
		dp = [0] * (n + 1)
		dp[0] = 1
		dp[1] = 1
		for i in range(2, n + 1):
			for j in range(1, i + 1):
				dp[i] += dp[i - j] * dp[j - 1]
		return dp[n] % int(1000000000.0 + 7)


class Solution:

	def numTrees(self, N):
		import math

		def GCD(a, b):
			if b == 0:
				return a
			else:
				return GCD(b, a % b)

		def nCr(n, r):
			if n - r < r:
				r = n - r
			(ne, de) = (1, 1)
			while r:
				ne = ne * n
				de = de * r
				val = math.gcd(ne, de)
				ne = ne // val
				de = de // val
				n -= 1
				r -= 1
			return ne
		return nCr(2 * N, N) // (N + 1) % 1000000007


from math import factorial as fac

class Solution:

	def numTrees(self, N):
		return fac(2 * N) // (fac(N + 1) * fac(N)) % (10 ** 9 + 7)


class Solution:

	def numTrees(self, N):
		dp = [0 for i in range(N + 1)]
		dp[0] = 1
		mod = 10 ** 9 + 7
		for i in range(1, N + 1):
			for j in range(1, i + 1):
				dp[i] += dp[j - 1] * dp[i - j]
				dp[i] %= mod
		return dp[N]


class Solution:

	def numTrees(self, N):
		dp = [-1] * (N + 1)
		dp[0] = 1
		dp[1] = 1
		MOD = 10 ** 9 + 7
		for i in range(2, N + 1):
			sum = 0
			for j in range(0, i):
				left = dp[j]
				right = dp[i - j - 1]
				sum = sum + left * right
			dp[i] = sum
		return dp[N] % MOD


class Solution:

	def catalan(self, N):
		if N == 0 or N == 1:
			return 1
		catalan = [0] * (N + 1)
		catalan[0] = 1
		catalan[1] = 1
		for i in range(2, N + 1):
			for j in range(i):
				catalan[i] += catalan[j] * catalan[i - j - 1]
		return catalan[n]

	def numTrees(self, N):
		return self.catalan(N) % (10 ** 9 + 7)


class Solution:

	def numTrees(self, n):
		dp = [0] * (n + 1)
		(dp[0], dp[1]) = (1, 1)
		for i in range(2, n + 1):
			for j in range(1, i + 1):
				dp[i] = dp[i] + dp[i - j] * dp[j - 1]
			dp[i] = dp[i] % 1000000007
		return dp[n]


MOD = 10 ** 9 + 7

class Solution:

	def numTrees(self, N):
		catalan = 1
		for i in range(1, N + 1):
			catalan *= 4 * i - 2
			catalan //= i + 1
		return catalan % MOD


mp = {}

def binTrees(n):
	if n in mp:
		return mp[n]
	if n == 1 or n == 0:
		return 1
	ans = 0
	for i in range(n):
		ans += binTrees(i) * binTrees(n - i - 1)
	mp[n] = ans % (10 ** 9 + 7)
	return ans % (10 ** 9 + 7)

class Solution:

	def numTrees(self, N):
		return binTrees(N)


class Solution:

	def numTrees(self, N):

		def fact(n):
			dp = [0 for i in range(n + 1)]
			x = 1
			for i in range(1, n + 1):
				x *= i
				dp[i] = x
			return dp[n]
		a = int(fact(2 * N) // (fact(N + 1) * fact(N)))
		return int(a % int(1000000000.0 + 7))


class Solution:

	def numTrees(self, N):
		dp = [-1 for _ in range(N + 1)]
		dp[0] = 1
		dp[1] = 1
		for i in range(2, N + 1):
			ans = 0
			for j in range(i):
				ans += dp[j] * dp[i - j - 1]
			dp[i] = ans
		modulo = 10 ** 9 + 7
		return dp[N] % modulo


class Solution:

	def numTrees(self, N):
		temp = 2 * N
		ans = 1
		while temp > 0:
			ans *= temp
			temp = temp - 1
		temp = N
		ans2 = 1
		while temp > 0:
			ans2 *= temp
			temp = temp - 1
		return ans // (ans2 * ans2) // (N + 1) % 1000000007


class Solution:

	def numTrees(self, N):
		dp = [0 for _ in range(N + 1)]
		dp[0] = 1
		dp[1] = 1
		for i in range(2, N + 1):
			for j in range(1, i + 1):
				dp[i] = (dp[i] + dp[j - 1] * dp[i - j] % 1000000007) % 1000000007
		return dp[N]
		return ans(N, dp)


class Solution:

	def numTrees(self, n, memo=dict()):
		if n in memo:
			return memo[n]
		if n == 0:
			return 1
		if n == 1:
			return 1
		res = 0
		for i in range(0, n):
			res += self.numTrees(i) * self.numTrees(n - i - 1)
		memo[n] = res % (10 ** 9 + 7)
		return memo[n]


def solve(n, dp):
	if n <= 1:
		return 1
	if dp[n] != -1:
		return dp[n]
	ans = 0
	for i in range(1, n + 1):
		ans += solve(i - 1, dp) % 1000000007 * (solve(n - i, dp) % 1000000007)
	dp[n] = ans % 1000000007
	return dp[n]

class Solution:

	def numTrees(self, n):
		dp = [-1] * (n + 1)
		return solve(n, dp)


class Solution:

	def __init__(self):
		self.mem = {}
		self.mod = 1000000007

	def numTrees(self, N):
		if N == 0 or N == 1:
			return 1
		if N in self.mem:
			return self.mem[N]
		count = 0
		for i in range(1, N + 1):
			count += self.numTrees(i - 1) * self.numTrees(N - i)
		self.mem[N] = count % self.mod
		return self.mem[N]


class Solution:

	def numTrees(self, N):
		t = {}

		def solve(i):
			if i == 1 or i == 0:
				return 1
			if i == 2:
				return 2
			if i in t:
				return t[i]
			temp = 0
			for j in range(1, i + 1):
				left = j - 1
				right = i - j
				temp += solve(left) * solve(right)
			t[i] = temp
			return t[i]
		return solve(N) % (10 ** 9 + 7)


class Solution:

	def numTrees(self, N):
		question_bank = {}

		def fun(n):
			if n == 0 or n == 1:
				return 1
			if n == 2:
				return 2
			if n in question_bank:
				return question_bank[n]
			count = 0
			for i in range(1, n + 1):
				left = i - 1
				right = n - i
				sub_left = fun(left)
				sub_right = fun(right)
				count += sub_left * sub_right
			question_bank[n] = count
			return question_bank[n]
		return fun(N) % (10 ** 9 + 7)


class Solution:

	def numTrees(self, n):
		m = 10 ** 9 + 7
		dp = [0] * (n + 1)
		(dp[0], dp[1]) = (1, 1)
		for i in range(2, n + 1):
			for j in range(1, i + 1):
				dp[i] = dp[i] + dp[i - j] * dp[j - 1]
		return dp[n] % m


class Solution:

	def numTrees(self, N):
		numTree = [1] * (N + 1)
		for nodes in range(2, N + 1):
			total = 0
			for root in range(1, nodes + 1):
				left = root - 1
				right = nodes - root
				total += numTree[left] * numTree[right]
			numTree[nodes] = total
		return numTree[N] % (10 ** 9 + 7)


class Solution:

	def numTrees(self, N):
		cat = 1
		for i in range(1, N + 1):
			cat *= 4 * i - 2
			cat //= i + 1
		cat %= 1000000007
		return cat