동적계획법

모든 알고리즘 문제들은 완전 탐색을 이용해 정답을 도출할 수 있다
단지 비효율적인 연산과 시간을 없애고 답을 효율적으로 도출하기 위해 여러 알고리즘 기법을 사용하는것
동적 계획법은 여러 유형의 문제들을 논리적인 사고를 이용해 효율적으로 풀 수 있는 사고방식

동적 계획법의 원리와 구현 방식
1. 큰 문제를 작은 문제로 나눌 수 있어야 한다
2. 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 한다
3. 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용 할 때는 이 DP테이블을 이용한다. 이를 메모이제이션 기법이라고 한다.
// 백트래킹 가지치기
4. 동적 계획법은 톱-다운 방식과 바텀-업 방식으로 구현할 수 있다.

피보나치 수열 공식
D[N] = D[N-1] + D[N-2] // N번째 수열 = N-1번째 수열 + N-2번째 수열

1. 동적 계획법으로 풀 수 있는지 확인하기
   6번째 피보나치 수열은 5번쨰 피보나치 수열과 4번째 피보나치 수열의 합이다. 즉 6번쨰 피보나치 수열을 구하는 문제는 5번째 피보나치 수열과 4번째 피보나치 수열을 구하는 작은 문제로 나눌 수 있고, 수열의 값은 항상 같기 때문에 동적 계획법으로 풀 수 있다.

2. 점화식 세우기
   점화식을 세울 때는 논리적으로 전체 문제를 나누고, 전체 문제와 부분 문제 간의 인과관계를 파악하는 훈련이 필요하다.

3. 메모이제이션 원리 이해하기

4. 톱-다운 구현 방식 이해하기
   위에서부터 문제를 파악해 내려오는 방식, 재귀 함수 형태로 코드를 구현

5. 바텀-업 구현 방식 이해하기
   가장 작은 부분 문제부터 문제를 해결하면서 점점 큰 문제로 확장해나가는 방식. 주로 반복문

두 방식 중 좀 더 안전한 방식은 바텀-업 방식이다. 톱-다운 방식은 재귀 함수의 형태로 구현돼있기 때문에 재귀의 깊이가 매우 깊어질 경우 런타임 에러가 발생할 수 있다.