• DP
  • 문제를 쪼개서 작은 문제의 답을 구하고, 그걸로 더 큰 문제의 답을 구하는 걸 반복
  • 분할정복
• 다이나믹 프로그래밍
  • 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있는가?
  • 중복되는 부분 문제 : 동일한 작은 문제를 반복적으로 해결되는가?
  • 구현 방법
    • Top Down : 구현 > 재귀, 저장방식 : 메모이제이션 > 한번 구한 답들을 저장해두는것(cache에 저장), 부분 문제들의 답을 한번 구했으면 또 구하지 않도록(중복연산 방지), 필요한 부분 문제들만 구한다(Lazy-Evaluation)
    • Bottom Up : 구현 > 반복문, 저장방식 : 타뷸레이션 > 부분 문제들의 답을 미리 다 구해두면 편하다!, 테이블을 채워나간다는 의미에서 타뷸레이션, 필요 없는 부분 문제들 까지 전부 구한다(Eager-Evaluation)