다이나믹 프로그래밍

문제를 쪼개서 작은 문제의 답을 구하고, 그걸로 더 큰 문제의 답을 구하는 것을 반복하는 알고리즘

분할정복과 비슷한 느낌이다.

DP 구현 2가지 방법

• Top-down
  • 구현 방법: 재귀
  • 저장 방식: Memoization
• Bottom-up
  • 구현 방법: 반복문
  • 저장 방식: Tabulation

Memoization

• 한 번 구한 답들은 저장해두자는 저장 방식이다.
• 즉, 부분 문제들의 답을 한 번 구했으면, 또 구하지 않도록 (중복연산 방지) cache에 저장해두고, 다음부터 가져다 쓰는 방식
• 필요한 부분 문제들만 구한다. (Lazy-Evaluation)

Tabulation

• 부분 문제들의 답을 미리 다 구해두면 편하다.
• 테이블을 채워간다는 의미이다.
• 필요 없는 부분 문제들까지 전부 구한다. (Eager-Evaluation)