# 5. DP

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

DP는 2가지 속성을 만족해야한다.

1. Overlapping SubProblem
   * 부분 문제가 겹친다.
2. Optimal Substructure
   * 최적부분 구조.

## 예제를 통해 DP 특징 파악하기

* F(0) = 0
* F(1) = 1
* F(N) = F(N-1) + F(N-2) (N>=2)
* Overlapping SubProblem
* 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다.
* 문제를 작은 문제로 쪼갤 수 있다.
* 문제 : N번째 피보나치 수를 구하기
* 작은 문제 : N-1번째 피보나치 수 구하기, N-2번쨰 피보나치 수 구하기
* Optimal Substructure
* 문제의 정답을 작은 문제의 정답에서 구할 수 있다.
* 2번을 만족한다면, 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다.

## DP 특징

* 각 문제는 한 번만 풀기
* Optimal Substructure를 만족하기 때문에, 같은 문제는 구할 때마다 정답이 같다.
* 따라서, 정답을 한 번 구했으면 정답을 어딘가 메모(memoization)

## 문제 풀이 전략

### bottom up

1. 점화식의 정의를 세운다. F(N) = F(N-1) + F(N-2);
2. 정의를 세우는 방법은?
   * 글로 나타내기
   * 피보나치 수의 경우 : N번쨰 피보나치수를 구하기.
     * N번째라는 변수가 1개 있으니 1차원 배열이면 됨.
   * D\[N] : N번쨰 피보나치 수
   * 어떻게 작은 문제로 쪼갤지 작성
   * D\[N-1], D\[N-2]
   * 이제 어떻게 원래의 문제를 풀 수 있는지 
   * D\[N] = D\[N-1] + D\[N-2];

의\
문제를 크기가 작은 문제부터 차례로 푼다.