'''
Динамическое программирование.
'''


def fib(n):
    '''
    поиск числа фибоначи
    ТАК ДЕЛАТЬ НЕПРАВИЛЬНО - ОЧЕНЬ БОЛЬШАЯ АСИМПТОТИКА
    количество оппераций при поиске числа фибоначи запредельное
    '''
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)


a = fib(30)
print(a)

'''поиск числа фибоначи 
ПРАВИЛЬНЫЙ ПОДХОД
линейная асимптотика! 
число фибоначи находится очень быстро
'''
n = 30
fib2 = [0, 1] + [0]*(n-1)
for i in range(2, n+1):
    fib2[i] = fib2[i-1] + fib2[i-2]

b = fib2[n]
print(b)
