[1028알고리즘 20]Dynamic Programming

피보나치 수열. _ 재귀함수.

1,1,2,3,4,8

1 + 1 = 2

fibo(1)=1

fibo(2)= 1

fibo(3) =fibo(1)+fibo(2)

fibo(n) = fibo(n-2) + fibo(n-1)

같은 계산을 N^n 반복.

결과를 기록해서 이용. = 메모이제이션  Memoization

문제를 쪼갤수 있는 구조= 겹치는 부분문제 = Overlapping subproblem.

input = 100

# memo 라는 변수에 Fibo(1)과 Fibo(2) 값을 저장해놨습니다!
memo = {
    1: 1,
    2: 1
}
# Top Down 방식.   반대는 바텀업


def fibo_dynamic_programming(n, fibo_memo):
    if n in fibo_memo:
        return fibo_memo[n]

    nth_fibo = fibo_dynamic_programming(n - 1, fibo_memo)+ fibo_dynamic_programming(n - 2, fibo_memo)
    fibo_memo[n] = nth_fibo
    # print(nth_fibo)
    return nth_fibo


print(fibo_dynamic_programming(input, memo))  # 354224848179261915075