큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다.

1. 1.Overlapping Subproblem (겹치는 부분문제)
2. 2.Optimal Substructure(문제의 정답을 작은 부분에서 알 수 있을 때) : 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

이 두가지 속성을 만족해야 다이나믹 프로그래밍으로 문제를 풀 수 있다.

Overlapping Subproblem

1. 1.큰 문제와 작은 문제를 같은 방법으로 풀 수 있다.
2. 2.문제를 작은 문제로 쪼갤 수 있다.

Optimal Substructure

문제의 정답을 작은 문제의 정답에서 구할 수 있다.

N-1번째 피보나치 수를 구하는 문제 = N-2번째 피보나치 수를 구하는 문제 + N-3번째 피보나치 수를 구하는 문제

다이나믹 프로그래밍

Top-down

1. 1.문제를 작은 문제로 나눈다.
2. 2.작은 문제를 푼다.
3. 3.작은 문제를 풀었으니, 이제 문제를 푼다.

재귀호출을 이용해서 문제를 쉽게 풀 수 있다. 시간복잡도는 채워야하는 칸의 수 X 한 칸을 채우는 복잡도(함수하나의 시간 복잡도)이다.

d = [0] * 100

def fibonacci_recursion(x):

    # 1 or 2 는 1
    if x == 1 or x == 2:
        return 1

    # 이미 한번 호출된 적 있는 값은 기억해둔 값 반환
    if d[x]!=0:
        return d[x]

    # 한번도 호출된적 없는 값은 추가
    d[x] = fibonacci_recursion(x-1) + fibonacci_recursion(x-2)
    return d[x]

print(fibonacci_recursion(6))

Bottom-up

1. 1.문제를 크기가 작은 문제부터 차례대로 푼다.
2. 2.문제의 크기를 조금씩 크게 만들면서 문제를 푼다.
3. 3.작은 문제를 풀면서 왔기 때문에, 큰 문제는 항상 풀 수 있다.

d = [0] * 100

def fibonacci_loop(n):
    d[1] = 1
    d[2] = 1

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

    print(d[n])