Sandbox::https://github.com/FullstackSensei/leetcode/blob/master/algorithms/python/FibonacciNumber/fib.py

Repository navigation

27 lines (25 loc) · 526 Bytes

"""

Method 1: iterative:

"""

def fib1(self, N):

if N <= 1: return N

a, b = 0, 1

for _ in range(2, N + 1):

a, b = b, a + b

return b

"""

Method 2: recursive without memorization:

"""

def fib2(self, N):

if N <= 1: return N

return self.fib(N - 1) + self.fib(N - 2)

"""

Method 3: recursive with memorization

"""

def fib3(self, N):

memo = {0:0, 1:1}

def helper(n):

if n not in memo:

memo[n] = helper(n - 1) + helper(n - 2)

return memo[n]

return helper(N)