AlgoDesignAndTechniqueEdxPython/sources/fibonacci.py


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# Uses python3
def calc_naive(n):
    if (n <= 1):
        return n
 
    return calc_naive(n - 1) + calc_naive(n - 2)

def calc_optimize1(n):
    if (n <= 1):
        return n
    fibLst = [None] * (n+1)
    fibLst[0] = 0
    fibLst[1] = 1
    for j in range(2, n+1):
        fibLst[j] = fibLst[j-1] + fibLst[j-2]
    return fibLst[n]

n = int(input())
print(calc_optimize1(n))