[이코테] Dynamic Programming - 피보나치

import time
d = [0] * 40

def fibo(x):
    if x == 1 or x == 2:
        return 1
    else:
        return fibo(x-1) + fibo(x-2)

def fibo_dynamic1(x): #top-down
    if x == 1 or x == 2:
        return 1
    if d[x] != 0:
        return d[x]
    d[x] = fibo_dynamic1(x-1) + fibo_dynamic1(x-2)
    return d[x]

d = [0] * 40

def fibo_dynamic2(x): #bottom-up
    d[0] = 1
    d[1] = 1
    for i in range(3, x):
        d[i] = d[i-1] + d[i-2]
    return d[x]

start = time.time()

print(fibo_dynamic1(39), "(time :", time.time()-start,")")

start = time.time()

print(fibo_dynamic2(39), "(time :", time.time()-start,")")

start = time.time()

print(fibo(39),"(time :", time.time()-start,")")

피보나치 함수를 만들어 동적 프로그래밍의 속도를 체험해보고자 했음

63245986 (time : 0.0 )
63245986 (time : 0.0 )
63245986 (time : 16.77222752571106 )

무쟈게 차이난다...

이건 모르면 그냥 무조건 타임아웃 뜨겠군