1. 정의

• 하나의 문제를 여러 작은 문제로 나누며 이를 결합하여 최종 답을 구하는 방식
• 분할-정복과의 차이 : 분할 정복은 큰 문제를 해결하기 어려워 작은 문제로 나누어 푸는 방법인 반면, 동적 계획법은 작은 부분 문제들이 반복되는 것을 이용해 풀어나가는 방법
• 동일한 작은 문제들이 반복되서 나오며, 중복되는 하위 문제가 많은 경우에 사용 가능
• 최적 부분 구조 : 문제의 최적 해결 방법이 부분 문제의 최적 해결 방법으로 구성된 문제 구조

2. 메모이제이션과 타뷸레이션

• 메모이제이션 : 하향식 방식에서, 부분 문제의 해를 캐시에 넣어 사용하는 기술
• 타뷸레이션 : 상향식 방식에서, 기저 조건 해답부터 시작하여 모든 부분 문제에 대한 해답을 표에 저장한 후 재사용하는 방식

3. 동적 계획법의 순서

• DP로 풀 수 있는지 확인
• 문제 간 변수 파악 후 점화식 만들기
• Memoization or Tabulation
• 기저 상태 파악
• 구현