동적 프로그래밍(dynamic programming)은 부분 문제가 중복되는 문제를 풀기 위한 전산학 기법이다. 중복되는 부분 문제를 계속 다시 푸는 대신 한 번만 풀고 그 결과를 표에 저장한 후 그 값으로부터 원래 문제에 대한 답을 구하는 방식이다. 동적 프로그래밍은 미국의 저명한 수학자 Richard Ernest Bellman이 1950년대에 발명한 것으로 다단계 의사결정 절차를 최적화하기 위한 일반화된 방법론으로 만들어진 것이다. 어떤 최적화 문제를 이 기법으로 풀기 위해서는 최적화된 부분 구조가 있어야 하며 부분 문제에 대한 최적해로부터 전체 문제에 대한 최적해를 효율적으로 구성할 수 있어야 한다.

최단 경로 개수를 찾아내는 문제를 예로 생각해보자.

최단 경로 개수 그림 1-11 (a)에 나와 있는 것처럼 모든 도로가 완전히 수평 또는 수직 방향으로만 나 있을 때 A 교차로에서 B 교차로로 이어지는 최단 경로 개수를 구하라.

▲ 그림 1-11 (a) 동적 프로그래밍으로 (i, j) 교차로까지 가는 최단 경로 개수를 구하는 방법. (b) A 교차로에서 각 교차로로 갈 수 있는 최단 경로 개수