27 lines
526 B
Python
27 lines
526 B
Python
"""
|
|
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) |