DP의 핵심요소는 메모이제이션(캐싱)이라고 할 수 있다. 이미 계산한 결과를 저장하는 재귀라고도 할 수 있다. 기억 공간을 반복될 계산결과의 저장에 할당함으로써 귀중한 연산시간을 절약하는 것이다. DP를 이용해 해결할 수 있는 대표적이며 가장 간단한 예로 피보나치 수열이 있다. 어떻게 이 문제가 재귀, top-down DP, bottom-up DP, 그리고 그 기억공간을 추가로 절감하는 방식으로 수행되는지를 살펴본다. 재귀 피보나치 수열은 수학적으로 다음 점화식(recurrence relation)으로 정의된다. $$ f_n = f_{n-1} + f_{n-2} $$ $$ f_0 = 0; \ f_1 = 1 $$ n번째 수를 구하기 위해서는 n-1번째, n-2번째 수를 알아야 하고, 그들을 알기 위해서는 다..