다이나믹 프로그래밍(Dynamic Programming)이란 무엇인가? 이것은 다이나믹 플래닝(Dynamic Planning)이란 개념과 비슷하다고 할 수 있다. 간단히 이야기해서, 실행 시간의 정보를 기록한다는 의미이다. 즉, 중복되는 계산 결과를 기록해서 중복된 계산 결과가 필요한 경우, 최대한 재계산을 피하고자 하는 것이다.
예를 들어서, 피보나치 수열의 경우, n항의 값을 알려주는 함수 fib(n)을 작성한다고 하자. f(n) = f(n - 2) + f(n - 1)이다. f(n)을 알기 위해서는, 앞의 두 항의 값을 알고 있어야 한다. f(5), f(6)을 계산할 때, fib(n)을 재귀호출 방식으로 작성한다면, 같은 항에 대해 연속적으로 재계산을 하게 된다. 만약, f(n)을 어딘가에 저장해두고, 이것을 필요할 때 호출하는 방식이라면, 약간의 메모리를 더 사용해서 최대한 재계산을 피할 수 있게 된다. 다이나믹 프로그래밍은, 이처럼 실행시간에서의 정보를 기록해두어서 최대의 효율성을 추구한다.
여기서 생각해봐야 할 것은, 과연 절약되는 연산량과 증가하는 메모리 사용량 중 어느 것이 효율적인가 여부이다.
Library/Algorithm