Dynamic Programming#
Fibonacci#
[18]:
# Recursion
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)
fib(34)
[18]:
5702887
[17]:
# Memoization using lookup tables, top down approach
def fib(n,lup):
if n <=1 :
lup[n] = n
if lup[n] is None:
lup[n] = fib(n-1,lup) + fib(n-2,lup)
return lup[n]
n = 34
lup = [None]*(n+1)
fib(n,lup)
[17]:
5702887
[22]:
# Using tabulation bottop-up approach
def fib(n):
# Decalre the table
ltable = [0]*(n+1)
# Assign base values
ltable[0],ltable[1]=0,1
# Fill the table
for i in range(2,n+1):
ltable[i] = ltable[i-1] + ltable[i-2]
return ltable[n]
fib(34)
[22]:
5702887