Dynamic Programming

DP 문제를 푸는 방법

다음과 같은 순서로 알고리즘을 개선해나가자.

1. recursive 관계를 찾아낸다.
2. recursive하게 알고리즘을 구현한다. (top-down)
3. recursive한 알고리즘에 memo[] 배열을 사용하여 반복을 줄인다. (top-down)
4. iterative한 알고리즘으로 바꿔본다. (bottom-up)
5. memo[] 배열 대신에 N개의 변수로 줄여본다. (bottom-up)