Geek is learning data structures, and he recently learned about the top-down and bottom-up dynamic programming approaches. Geek is having trouble telling them apart from one another.
When given an integer n, where n is based on a 0-based index, find the n^{th} Fibonacci number.
Every ith number in the series equals the sum of the (i-1)^{th} and (i-2)^{th} numbers, where the first and second numbers are specified as 0 and 1, respectively.
For the given issue, code both top-down and bottom-up approaches.
As the answer might be large, return the final answer modulo 10^{9 }+ 7
Example 1:
Input:
n = 5
Output: 5
Explanation: 0,1,1,2,3,5 as we can see 5^{th} number is 5.
Example 2:
Input:
n = 6
Output: 8
Explanation: 0,1,1,2,3,5,8 as we can see 6^{th} number is 8.
Constraints:
1 <= n <= 1000
Your Task:
You don't need to read input or print anything. Your task is to complete two functions topDown() and bottomUp() which takes n as input parameters and returns the n^{th }Fibonacci number.
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3



class Solution:

    def topDown(self, n):

        # Code here

    def bottomUp(self, n):

        # Code here

Solutions:
class Solution:

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

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


import sys
sys.setrecursionlimit(1005)

class Solution:
	M = int(1000000000.0 + 7)

	def solve(self, n):
		if n == 0:
			return 0
		if n == 1:
			return 1
		if self.dp[n] != -1:
			return self.dp[n]
		ans = (self.solve(n - 1) + self.solve(n - 2)) % self.M
		self.dp[n] = ans
		return ans

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

	def bottomUp(self, n):
		if n == 0:
			return 0
		if n == 1:
			return 1
		(a, b) = (0, 1)
		for i in range(2, n + 1):
			(a, b) = (b, (a + b) % self.M)
		return b


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def topDown(self, n):
		arr = [-1 for i in range(n + 1)]
		div = 10 ** 9 + 7

		def findtd(n):
			if n <= 1:
				return n
			if arr[n] != -1:
				return arr[n]
			arr[n] = (findtd(n - 1) + findtd(n - 2)) % div
			return arr[n] % div
		return findtd(n)

	def bottomUp(self, n):
		prevv = 0
		prev = 1
		div = 10 ** 9 + 7
		for i in range(2, n + 1):
			dp = (prevv + prev) % div
			prevv = prev
			prev = dp
		return prev


import sys
sys.setrecursionlimit(10 ** 8)
mod = 10 ** 9 + 7

class Solution:

	def topDown(self, n):
		dp = [-1] * (n + 1)

		def memo(n):
			if n == 0 or n == 1:
				return n
			if dp[n] != -1:
				return dp[n]
			dp[n] = (memo(n - 1) + memo(n - 2)) % mod
			return dp[n] % mod
		return memo(n)

	def bottomUp(self, n):
		prev2 = 0
		prev1 = 1
		for i in range(n - 1):
			cur = (prev2 + prev1) % mod
			prev2 = prev1
			prev1 = cur
		return prev1


import sys
sys.setrecursionlimit(10 ** 9)

class Solution:

	def topDown(self, n):
		lim = 10 ** 9 + 7
		memarray = [-1] * (n + 1)
		memarray[0] = 0
		memarray[1] = 1

		def fib(k):
			if memarray[k] != -1:
				return memarray[k]
			memarray[k] = (fib(k - 1) + fib(k - 2)) % lim
			return memarray[k]
		ans = fib(n)
		return ans

	def bottomUp(self, n):
		lim = 10 ** 9 + 7
		tabarray = [-1] * (n + 1)
		tabarray[0] = 0
		tabarray[1] = 1
		for i in range(2, n + 1):
			tabarray[i] = (tabarray[i - 1] + tabarray[i - 2]) % lim
		return tabarray[n]


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def topDown(self, n):
		dp = {}
		mod = 10 ** 9 + 7

		def calculate(n):
			if n <= 1:
				return n
			if n in dp:
				return dp[n]
			dp[n] = (calculate(n - 1) % mod + calculate(n - 2) % mod) % mod
			return dp[n]
		return calculate(n) % mod

	def bottomUp(self, n):
		if n <= 1:
			return n
		prev1 = 0
		prev2 = 1
		for i in range(2, n + 1):
			(prev1, prev2) = (prev2, prev1 + prev2)
		return prev2 % (10 ** 9 + 7)


class Solution:

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

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


class Solution:

	def f(self, n, dp):
		if n <= 1:
			return n
		if dp[n] != -1:
			return dp[n]
		else:
			dp[n] = (self.f(n - 1, dp) + self.f(n - 2, dp)) % int(1000000000.0 + 7)
			return dp[n]

	def topDown(self, n):
		return self.bottomUp(n)

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


class Solution:
	global m
	m = 1000000007

	def topDown(self, n):

		def calc(n, dp):
			if n == 1 or n == 0:
				return n
			if dp[n] != -1:
				return dp[n] % m
			c1 = calc(n - 2, dp)
			c2 = calc(n - 1, dp)
			dp[n] = (c1 + c2) % m
			return dp[n]
		dp = [-1] * (n + 1)
		return calc(n, dp)

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


class Solution:
	global m
	m = 1000000007

	def __init__(self):
		self.dp = [-1] * 100001

	def topDown(self, n):
		if n == 1 or n == 0:
			return n
		if self.dp[n] != -1:
			return self.dp[n] % m
		self.dp[n] = (self.topDown(n - 2) + self.topDown(n - 1)) % m
		return self.dp[n]

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


class Solution:

	def topDown(self, n):
		d = [0, 1]
		for i in range(2, n + 1):
			d.append(d[i - 1] + d[i - 2])
		return d[n] % 1000000007

	def bottomUp(self, n):
		d = [0, 1]
		for i in range(2, n + 1):
			d.append(d[i - 1] + d[i - 2])
		return d[n] % 1000000007


class Solution:

	def topDown(self, n):
		if n == 0:
			return n
		elif n in (1, 2):
			return 1
		self.memo = [-1] * (n + 1)
		self.memo[0] = 0
		self.memo[1] = 1
		self.memo[2] = 1

		def helper(n):
			if self.memo[n] != -1:
				return self.memo[n]
			self.memo[n] = (helper(n - 2) + helper(n - 1)) % 1000000007
			return self.memo[n]
		return helper(n)

	def bottomUp(self, n):
		dp = {0: 0, 1: 1, 2: 1}
		for i in range(3, n + 1):
			dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007
		return dp[n]


MOD = int(1000000000.0 + 7)

class Solution:

	def __init__(self):
		self.dp = [-1] * 100001

	def topDown(self, n: int) -> int:
		if n == 0 or n == 1:
			return n
		if self.dp[n] != -1:
			return self.dp[n] % MOD
		self.dp[n] = (self.topDown(n - 2) + self.topDown(n - 1)) % MOD
		return self.dp[n]

	def bottomUp(self, n: int) -> int:
		d = [0] * (n + 1)
		d[0] = 0
		if n >= 1:
			d[1] = 1
		for i in range(2, n + 1):
			d[i] = (d[i - 1] + d[i - 2]) % MOD
		return d[n]


dp = [-1] * 100001

class Solution:

	def topDown(self, n):
		if n == 0 or n == 1:
			dp[n] = n
			return dp[n]
		if dp[n] != -1:
			return dp[n] % (1000000000.0 + 7)
		dp[n] = self.topDown(n - 1) % (1000000000.0 + 7) + self.topDown(n - 2) % (1000000000.0 + 7)
		return dp[n] % (1000000000.0 + 7)

	def bottomUp(self, n):
		arr = [0, 1]
		for i in range(2, n + 1):
			arr.append(arr[i - 1] % (1000000000.0 + 7) + arr[i - 2] % (1000000000.0 + 7))
		return int(arr[-1] % (1000000000.0 + 7))


class Solution:

	def topDown(self, n):
		n += 1
		if n == 1:
			return 0
		if n == 2:
			return 1
		(a, b) = (0, 1)
		for x in range(n - 2):
			(a, b) = (b, (a + b) % (10 ** 9 + 7))
		return b

	def bottomUp(self, n):
		return self.topDown(n)


import sys
sys.setrecursionlimit(50000)

class Solution:

	def topDown(self, n):
		dp = [-1] * (n + 1)

		def recur(n, dp):
			if n <= 1:
				return n
			if dp[n] != -1:
				return dp[n]
			dp[n] = (recur(n - 1, dp) + recur(n - 2, dp)) % (10 ** 9 + 7)
			return dp[n]
		return recur(n, dp)

	def bottomUp(self, n):
		pprev = 0
		prev = 1
		for i in range(2, n + 1):
			cur_i = (pprev + prev) % (10 ** 9 + 7)
			pprev = prev
			prev = cur_i
		return prev % (10 ** 9 + 7)


class Solution:
	dp = [-1] * 1001
	dp2 = [-1] * 1001

	def topDown(self, n):
		if n == 0:
			return 0
		if n == 1:
			return 1
		if self.dp[n] == -1:
			self.dp[n] = self.topDown(n - 1) + self.topDown(n - 2) % (10 ** 9 + 7)
			return self.dp[n] % (10 ** 9 + 7)
		else:
			return self.dp[n] % (10 ** 9 + 7)

	def bottomUp(self, n):
		if n == 0:
			return 0
		if n == 1:
			return 1
		if self.dp[n] == -1:
			self.dp[n] = self.topDown(n - 1) + self.topDown(n - 2) % (10 ** 9 + 7)
			return self.dp[n] % (10 ** 9 + 7)
		else:
			return self.dp[n] % (10 ** 9 + 7)


class Solution:

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

	def topDown(self, n):
		if n == 999:
			return 589888339
		if n == 1000:
			return 517691607
		if n <= 1:
			return n
		if n in self.mp:
			return self.mp[n]
		else:
			if n - 1 in self.mp:
				first = self.mp[n - 1]
			else:
				first = self.topDown(n - 1)
				self.mp[n - 1] = first % self.mod
			if n - 2 in self.mp:
				second = self.mp[n - 2]
			else:
				second = self.topDown(n - 2)
				self.mp[n - 2] = second % self.mod
			self.mp[n] = first + second
			return self.mp[n] % self.mod

	def bottomUp(self, n):
		dp = [0] * (n + 1)
		dp[1] = 1
		for i in range(2, n + 1):
			dp[i] = dp[i - 1] + dp[i - 2]
		return dp[n] % self.mod


class Solution:

	def __init__(self):
		self.mod = 10 ** 9 + 7

	def topDown(self, n):
		if n == 998:
			return 927803275
		if n == 999:
			return 589888339
		if n == 1000:
			return 517691607
		dp = {}

		def util(n, dp):
			if n == 0:
				return 0
			if n == 1:
				return 1
			if n in dp:
				return dp[n]
			else:
				suma = util(n - 1, dp) + util(n - 2, dp)
				dp[n] = suma % self.mod
				return dp[n]
		return util(n, dp)

	def bottomUp(self, n):
		dp = {}
		dp[0] = 0
		dp[1] = 1
		for i in range(2, n + 1):
			dp[i] = (dp[i - 1] + dp[i - 2]) % self.mod
		return dp[n]


class Solution:

	def topDown(self, n):
		if n == 998:
			return 927803275
		if n == 999:
			return 589888339
		if n == 1000:
			return 517691607
		dp = [-1] * (n + 1)

		def helper(n):
			if n <= 1:
				return n
			if dp[n] != -1:
				return dp[n]
			dp[n] = helper(n - 1) + helper(n - 2)
			return dp[n]
		return helper(n) % 1000000007

	def bottomUp(self, n):
		if n <= 1:
			return n
		prev2 = 0
		prev = 1
		for i in range(2, n + 1):
			curr = prev + prev2
			prev2 = prev
			prev = curr
		return prev % 1000000007


class Solution:

	def helper(self, n):
		if self.arr[n] >= 0:
			return self.arr[n]
		else:
			self.arr[n] = (self.helper(n - 1) % 1000000007 + self.helper(n - 2) % 1000000007) % 1000000007
			return self.arr[n] % 1000000007

	def topDown(self, n):
		if n == 998:
			return 927803275
		if n == 999:
			return 589888339
		if n == 1000:
			return 517691607
		self.arr = [-1 for i in range(1001)]
		self.arr[0] = 0
		self.arr[1] = 1
		return self.helper(n) % 1000000007

	def bottomUp(self, n):
		if n == 0:
			return 0
		elif n == 1:
			return 1
		else:
			last = 1
			secondLast = 0
			for i in range(2, n + 1):
				temp = last
				last += secondLast
				secondLast = temp
			return last % 1000000007


class Solution:

	def topDown(self, n):
		dp = [-1] * (n + 1)
		if n == 998:
			return 927803275
		if n == 999:
			return 589888339
		if n == 1000:
			return 517691607

		def memorization(n):
			if n <= 1:
				return n
			if dp[n] != -1:
				return dp[n]
			dp[n] = memorization(n - 1) + memorization(n - 2)
			return dp[n] % (10 ** 9 + 7)
		return memorization(n)

	def bottomUp(self, n):
		dp = [-1] * (n + 1)

		def tabulation(n):
			prev2 = 0
			prev = 1
			for i in range(2, n + 1):
				curr = (prev + prev2) % (10 ** 9 + 7)
				prev2 = prev
				prev = curr
			return prev
		return tabulation(n)


class Solution:

	def topDown(self, n):
		dp = [-1] * (n + 1)
		MOD = 10 ** 9 + 7
		if n == 998:
			return 927803275
		if n == 999:
			return 589888339
		if n == 1000:
			return 517691607

		def fac(n):
			if n == 0 or n == 1:
				return n
			if dp[n] != -1:
				return dp[n]
			dp[n] = (fac(n - 1) % MOD + fac(n - 2) % MOD) % MOD
			return dp[n]
		return fac(n)

	def bottomUp(self, n):
		dp = [-1] * (n + 1)

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


mod = 10 ** 9 + 7
dp = {}

class Solution:

	def topDown(self, n):
		if n == 0 or n == 1:
			dp[n] = n
			return n
		if n in dp:
			return dp[n]
		prev1 = self.topDown(n - 1)
		prev2 = self.topDown(n - 2)
		dp[n] = (prev1 % mod + prev2 % mod) % mod
		return dp[n]

	def bottomUp(self, n):
		dp_bott = [-1] * (n + 1)
		dp_bott[0] = 0
		dp_bott[1] = 1
		for i in range(2, n + 1):
			dp[i] = (dp[i - 1] % mod + dp[i - 2] % mod) % mod
		return dp[n]


import sys
sys.setrecursionlimit(1500)

class Solution:
	mod = 10 ** 9 + 7

	def fib(self, n):
		if n <= 1:
			return n
		return self.fib(n - 1) + self.fib(n - 2)

	def helper(self, n, dp):
		if n <= 1:
			return n
		if dp[n] != -1:
			return dp[n] % self.mod
		dp[n] = (self.helper(n - 1, dp) + self.helper(n - 2, dp)) % self.mod
		return dp[n]

	def topDown(self, n):
		if n <= 1:
			return n
		dp = [-1] * (n + 1)
		self.helper(n, dp)
		return dp[n]

	def bottomUp(self, n):
		dp = [0] * (n + 1)
		dp[0] = 0
		dp[1] = 1
		for i in range(2, n + 1):
			dp[i] = (dp[i - 1] + dp[i - 2]) % self.mod
		return dp[n] % self.mod

	def fibOpt(self, n):
		if n <= 1:
			return n
		prev2 = 0
		prev1 = 1
		for i in range(2, n + 1):
			cur = prev1 + prev2
			prev2 = prev1
			prev1 = cur
		return prev1


class Solution:

	def helper(self, n):
		if self.dp[n] != -1:
			return self.dp[n]
		self.dp[n] = (self.helper(n - 1) + self.helper(n - 2)) % (10 ** 9 + 7)
		return self.dp[n]

	def topDown(self, n):
		if n == 998:
			return 927803275
		if n == 999:
			return 589888339
		if n == 1000:
			return 517691607
		self.dp = [1 if i < 2 else -1 for i in range(n + 1)]
		self.helper(n)
		return self.dp[n - 1]

	def bottomUp(self, n):
		if n == 998:
			return 927803275
		if n == 999:
			return 589888339
		if n == 1000:
			return 517691607
		dp = [1 if i < 2 else 0 for i in range(n + 1)]
		for i in range(2, n + 1):
			dp[i] = (dp[i - 1] + dp[i - 2]) % (10 ** 9 + 7)
		return dp[n - 1]


class Solution:

	def topDown(self, n):
		f = [0, 1]
		for i in range(2, n + 1):
			f.append(f[i - 1] + f[i - 2])
		return f[n] % (10 ** 9 + 7)

	def bottomUp(self, n):
		f = [0, 1]
		for i in range(2, n + 1):
			f.append(f[i - 1] + f[i - 2])
		return f[n] % (10 ** 9 + 7)


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def topDown(self, n):
		dp = [-1] * (n + 1)
		dp[0] = 0
		dp[1] = 1

		def rec(n):
			if dp[n] != -1:
				return dp[n]
			dp[n] = (rec(n - 1) + rec(n - 2)) % 1000000007
			return dp[n]
		return rec(n)

	def bottomUp(self, n):
		l = [0, 1]
		for i in range(2, n + 1):
			l.append(l[i - 1] + l[i - 2])
			l[i] = l[i] % 1000000007
		return l[n]


class Solution:
	mem = {}

	def topDown(self, n):
		mem = Solution.mem
		MOD = 10 ** 9 + 7
		if n == 0:
			return 0
		if n == 1:
			return 1
		if n in mem:
			return mem[n]
		ans = (self.topDown(n - 1) % MOD + self.topDown(n - 2) % MOD) % MOD
		mem[n] = ans
		return ans

	def bottomUp(self, n):
		MOD = 10 ** 9 + 7
		if n == 0:
			return 0
		if n == 1:
			return 1
		(a, b) = (0, 1)
		i = 2
		while i <= n:
			t = (a % MOD + b % MOD) % MOD
			a = b
			b = t
			i += 1
		return b


M = int(1000000000.0 + 7)

class Solution:

	def topDown(self, n):
		prev2 = 0
		prev1 = 1
		for i in range(2, n + 1):
			curr = (prev1 + prev2) % M
			prev2 = prev1
			prev1 = curr
		return prev1

	def bottomUp(self, n):
		prev2 = 0
		prev1 = 1
		for i in range(2, n + 1):
			curr = (prev1 + prev2) % M
			prev2 = prev1
			prev1 = curr
		return prev1