[白俊]2748号フィボナッチ2

'''2021.08.30 풀이 
    백준 2748 피보나치2
    중복없애기 -> 다이나믹 프로그래밍 DP
    
    동적 프로그래밍 : 저장소를 두고 나온 결과는 임시저장하고 다시 계산하지 않는 것
    풀이 : 저장소 cache를 두고 푼다. (topdown 방식, bottomup 방식)
    '''

# topdown 방식
def fib(cache, n):
    if cache[n] != -1: #비어 있는지 확인
        return cache[n]
    if n == 0:
        cache[n] = 0
        
    elif n == 1:
        cache[n] = 1
        
    else:
        cache[n] =  fib(cache, n-1) + fib(cache, n-2)
    return cache[n]

def solve():
    n = int(input())
    cache = [-1 for _ in range(n+1)] #초기화
    print(fib(cache, n))

solve()
------------------------------------------------------------
# bottomup 방식 : 밑부터 하나씩 채워 넣는다.
def solve():
    n = int(input())
    arr = [0, 1]  #초기화
    for i in range(2, n+1):
        value = arr[i-1] + arr[i-2]
        arr.append(value)
    print(arr[n])

    solve()