Introduction.py

# dynamic programming is like a recursion but here we will only deal with the case the 
# subproblem is repeating itself.


# Fibonacci solution with the help of DP : 

deffibonacci(n,dp):
ifn==1orn==0: # base case
returnn
ifdp[n-1] ==-1: # checking if value is not stored in the dp array
ans1=fibonacci(n-1,dp)
dp[n-1] =ans1# Also update the dp array after finding the value.
else: # if stored in the dp array then just use that value from there.
ans1=dp[n-1]
ifdp[n-2] ==-1 :
ans2=fibonacci(n-2,dp)
dp[n-2] =ans2
else:
ans2=dp[n-2]

returnans1+ans2


# Iterative solution :

deffibbI(n):
dp= [0foriinrange(n+1)] # creating a dp array within the function
dp[0] =0
dp[1] =1
i=2
whilei<=n:
dp[i] =dp[i-1] +dp[i-2] # make a relation between the dp array elements by using the recursive relation.
i+=1
returndp[n]


# main

n=int(input())
dp= [-1foriinrange(n+1)]
print(fibonacci(n,dp))
print(fibbI(n))