DP

문제를 쪼개서 작은문제의 답을 구하고 그것을 이용해 더 큰 문제의 답을 구하는 방식
분할정복과 비슷

DP를 구현하는 2가지 방법

• Top-Down
  구현 : 재귀
  저장 방식 : 메모이제이션 (memoization)
• Bottom-Up
  구현 : 반복문
  저장 방식 : 타뷸레이션 (tabulation)

메모이제이션 (memoization)

한 번 구한 답들은 다시 새로 구하지 않도록 저장해두자
cache에 저장해두고 바로 갖다 쓰자
필요한 부분의 문제들의 답만 구해놓는다 ( Lazy-Evalutaion)
빈 dp 테이블에 필요한 곳에만 답을 채워놓는 식

타뷸레이션 (tabulation)

부분문제들의 답을 미리 다 구해놓는다 (Eager - Evalutation)
dp 테이블에 모두 값을 채워놓는다고 해서 타뷸레이션이라고 함