동적 프로그래밍은 큰 문제의 해답에 작은 문제의 해답이 포함되어 있고, 이를 재귀호출 알고리즘으로 구현하면 지나친 중복이 발생하는 경우에 이 재귀적 중복을 해결하는 방법을 의미한다.

재귀호출에 대해서는 이전에도 한번 공부한 적이 있다. 이 재귀호출의 장점은, 관계중심으로 문제를 파악하기 때문에 문제를 간명하게 볼 수 있다는 점이다. 하지만 치명적인 단점이 있다. 심각한 중복이 발생한다는 것이 그것이다. 이를 해결하기 위해 등장한 것이 바로 이 '동적 프로그래밍'이다.

어떤 문제를 동적 프로그래밍으로 풀어야 하는가

가장 익숙하지만, 전형적인 동적 프로그래밍의 예가 한가지 있다.

바로 '피보나치 수열' 이다.

피보나치 수열은 다음과 같이 정의된다.

$f(n) = f(n-1) + f(n -2)$

$f(1) = f(2) = 1$

즉, n의 피보나치는 n-1과 n-2 피보나치를 포함하고 있다. 이렇게 큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있으면, 이를 최적 부분 구조를 가졌다고 한다.

이러한 최적 부분 구조를 가져야 동적 프로그래밍을 적용하여 문제를 해결할 수 있다.

피보나치 수열을 재귀호출을 통해 해결해보자.

fib(n) {
	if (n ==1 || n == 2) {
		then return 1;
	else {
		return fib(n - 1) + fib(n -2);
}

n = 7 이라고 하자.

                                   fib(7)

             fib(6)                         fib(5)

 fib(5) fib(4)                 fib(4) fib(3)

fib(4) fib(3) fib(3) fib(2)   fib(3) fib(2) fib(2) fib(1)

fib(3) fib(2) fib(2) fib(1) fib(2) fib(1) ....

fib(7)을 구하는 과정에서 fib(5)는 2번, fib(3)은 5번 fib(2)는 8번이나 호출된다.

수가 점차 증가할 수록 이러한 중복문제는 심각해진다. 적어도 2의 n/2승 이상의 비율로 중복호출 횟수가 증가한다. n = 10이면, fib(2)가 무려 34번이나 호출된다..