동적계획법(Dynamic Programming)이란?

동적계획법은 복잡한 문제를 반복적인 작은 문제 단위로 나누어 푸는 방식을 뜻한다. 가장 흔한 방식이 메모이제이션을 이용하는 방법인데, 이는 간단하게 생각하면 중복된 연산을 피하기 위해 값들을 저장해나가며 값이 필요할 때 연산을 다시 하지 않고 메모이제이션으로 저장된 값을 꺼내 사용하는 식이다. 이를 다른 말로 캐싱이라고도 한다.

Top Down 방식

위에서 아래로 향하며 문제 해결하는 방식. 보통 재귀함수를 이용한다.

Bottom Up 방식

아래에서 위로 향하며 문제 해결하는 방식.