# This function uses the dynamic programming concept, where it stores previously computed values rather
# computing it every time like in normal recursion.

import time


# This version of fibonacci uses dynamic programming concept.
# First check the normal fibonacci.py for better understanding
def fibo_dp(n: int):  # pass 'n' to this function and it should be of type int
    memo = {}  # create an empty dictionary to hold the already calculated items
    if n < len(memo):  # if 'n' is less than the length of memo, then it already has that value stored in it
        return memo.get(n)  # then return that value
    else:
        if n <= 2:
            f = 1  # if 'n' is less than 2 then the value of f is 1
        else:
            f = fibo_dp(n - 1) + fibo_dp(n - 2)  # otherwise call the recursion
        memo[n] = f  # store it in memo for future use
        return f   # return the value to the calling function


if __name__ == "__main__":
    start_time = time.clock()  # starting the timer
    print(fibo_dp(15))  # calling the function here to find 700th number in fibonnaci series.
    print(time.clock() - start_time)  # print the finish time
