다이나믹 프로그래밍

- 다이나믹 프로그래밍 -> 큰 문제를 작은 문제로 나눠서 푸는 알고리즘

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

1. Overlapping Subproblem : 겹치는 부분문제
2. Optimal Substructure : 최적 부분구조

- 다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야 함.

- Optimal Substructure를 만족하기 때문에, 같은 문제는 구할 때마다 정답이 같음.

- 정답을 한 번 구했으면 그 값을 배열에 저장해둔다. (Memoization)

 

- 다이나믹 프로그래밍의 구현 방식에는 두 가지 방법이 있다.

1. Top-down : 큰 문제부터 쪼개가면서 작은 문제를 만들고 합쳐가면서 원래 문제를 푸는 방식
2. Bottom-up : 작은 문제들을 모아서 큰 문제 하나 만들고, 또 다시 반복해서 푸는 방식

- Top-down은 재귀 호출을 이용해서, Botton-up은 반복문을 이용해서 문제를 해결함.

 

- 다이나믹 프로그래밍 문제 풀이 전략

1. 문제에서 구해야하는 것을 점화식으로 세우고
2. 마지막 1단계가 무엇인지 찾고 (그 단계가 빠지면 문제가 작아지므로) 
3. 어떻게 변화가 되는지 보고 답을 찾는다.