다이나믹 프로그래밍은 동적 계획법이라 말한다.

다이나믹 프로그래밍은 문제가 다음 조건을 만족할 때 사용할 수 있다.(중요)

1. 최적 부분 구조(Optimal Substructure)
   • 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아 큰 문제를 해결 할 수 있는 것
2. 중복되는 부분 문제(Overlapping Subproblem)
   • 동일한 작은 문제를 반복적으로 해결해야 한다.

탑다운 방식 같은 경우 재귀함수를 사용한다. 다운탑 방식 같은 경우 loop 함수를 사용한다.

메모이제이션 동작 분석

문제 1

문제 2

문제 3

문제 4

문제 5