[온라인 : 기본 알고리즘] 다이나믹 프로그래밍

 

 

# 피보나치 수열

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

# 피보나치 수열 : 메모리제이션 방식

d = [0] * 100

def fibo_top_down(x):
    if x == 1 or x == 2:
        return 1
    if d[x] != 0:
        return d[x]
    d[x] = fibo(x - 1) + fibo(x - 2)
    return d[x]

# 피보나치 수열 : 바텀업 방식
d = [0] * 100

d[1] = 1
d[2] = 1
n = 99

for i in range(3, n+1):
    d[i] = d[i - 1] + d[i + 2]

print(d[n])