1. Dynamic Programming(동적계획법)
문제를 쪼개서 작은 문제의 답을 구하고, 그걸로 더 큰 문제의 답을 구하는 걸 반복한다. (분할정복과 비슷하다)
2. DP의 구현
- Top-Down
- Bottom-up
2.1. Memoization
- 부분 문제들의 답을
cache에 저장해두어 중복연산을 방지한다. - 필요한 부분 문제들만 구한다. (
Lazy-Evaluation) - Top-down 방식에서 사용한다.
2.2. Tabulation
- 부분 문제들의 답을 미리 다 구해둔다.
- 필요 없는 부분 문제들까지 전부 구한다. (
Eager-Evaluation) - Bottom-up 방식에서 사용한다.
- 테이블을 채워나간다는 의미라서
Tabulation이다.
