1. 개념

• 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법

2. 예시

2.1 피보나치 수열

• 설명: 이전 두 수의 합이 다음 수를 정의함
• 예: [1, 1, 2, 3, 5, 8, 13,...]

2.2 동적 계획법을 이용한 계산

2.2.1 문제

• 피보나치 수열의 100번째를 구해보자

2.2.2 해결방법(코드)

input = 100

memo = {
    1: 1,
    2: 1,
}


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

    return nth_fibo