def fib(n):
if n < 0:
return
if n <=1:
return n
else:
return fib(n-1) + fib(n-2)
Iterative
def fibdp(n):
f = [0]*(n+1)
f[1], f[0] = 1, 0
for i in range(2, n+1):
f[i] = f[i-1] + f[i-2]
#f[i] += f[i-1] + f[i-2]
Recursive + Memo
def fibMemo(n, memo):
if memo[n]:
return memo[n]
if 0<= n <=1:
result = n
else:
result = fibdp(n-1, memo) + fibdp(n-2, memo)
memo[n] = result
return result
memo = [None for _ in range(num+1)]
fibMemo(num, memo)
