[재귀/ BaekJoon] # 10870 피보나치 수 5

백준 10870번
피보나치 수

풀이1. 재귀 + 메모이제이션

• 탑다운 : 재귀다운 풀이

def fibo_func(n):
    if n < 2:
        return n
        
    if fibo[n]:
        return fibo[n]
        
    fibo[n] = fibo_func(n-1) + fibo_func(n-2)
    return fibo[n]
    
n = eval(input())
fibo = [None] * (n+1)
print(fibo_func(n))

풀이2. 반복문

• 바텀업 : 이 방법은 계산이 중복되지 않아서 깔끔한 것 같아요

n = eval(input())

fibo = [None] * (n+1)
for i in range(n+1):
	if i < 2:
   		return n
    
    fibo[n] = fibo[n-1] + fibo[n-2]

return fibo[n]