동적 계획법의 접근 방식은 기본적으로 분할 정복 알고리즘과 비슷하다. 동적 계획법을 사용하는 알고리즘 역시 주어진 문제를 부분 문제로 나누어 각 부분 문제의 답을 계산하고, 이 계산한 결과값을 이용해 원래 문제의 답을 산출하기 때문이다. 여기서 분할정복과 차이가 생기는 부분은 원래의 문제를 부분 문제로 나누는 방식에 있다. 동적 계획법의 경우 주어진 문제를 나눌 때 부분 문제를 최대한 많이 이용하도록 나눈 다음, 주어진 부분 문제의 정답을 한 번만 계산하고 저장해둔 뒤 다시 한 번 이 부분 문제를 이용할 때에는 저장해둔 정답을 바로 산출하여 이용함으로써 속도를 향상시킨다.

동적 계획법을 영문으로는 다이나믹 프로그래밍(dynamic programming)이라 표기하는데, 일반적으로 전산학에서 이용하는 프로그래밍이라는 단어와는 큰 연관이 없다.[1]

동적 계획법의 개념과 구현에 대해 정확하게 짚고 넘어가기 위해 동적 계획법을 적용시킬 수 있는 예에 대해 알아보자.

• f(a,b) = f(a-1,b) + f(a,b-1) (a,b >= 1 )
• f(0,0) = 1, 임의의 자연수 n에 대해 f(n,0) = f(0,n) = 1
  

위와 같이 정의된 함수에서 주어진 임의의 a,b에 대해 f(a,b)의 값을 효율적으로 구하고자 할 때 동적 계획법을 적용시킬 수 있다.

예를 들어 f(2,2)을 계산한다고 해보자. 이 경우 아래 그림과 같은 참조를 거치게 된다.

순서대로 계산횟수를 구해보면 f(2,2)를 구하기 위해 총 6번의 연산을 거쳐야한다. 이 때 중복되는 부분 문제[2]에 대한 답을 미리 계산해놓고 연산한다고 가정했을 때 계산횟수를 구해보면 f(2,2)를 구하기 위해 5번의 연산을 거쳐야한다. 이 경우 간단한 예라 중복되는 부분 문제가 f(1,1) 하나 뿐이기 때문에 큰 속도의 이득을 볼 수 없지만 a,b의 값이 커질 수록 속도 면에서 엄청난 이득을 볼 수 있다. 몇 가지 a,b 값에 대해 f(a,b)를 구하기 위한 연산 횟수를 나타낸 아래 표를 참조해보자.

(a,b)	그냥 계산시 연산 횟수	동적 계획법 이용시 연산 횟수
(2,2)	6	5
(4,4)	70	17
(6,8)	3003	49
(10,10)	184756	101

이 정도면 아마 대충 동적 계획법의 효율이 느껴질 것이다. 실제로 a,b가 1증가할 때마다 연산 횟수는 기하급수적으로 증가하며, 이 때 중복되는 부분 문제를 적절히 처리해줌으로써 높은 계산효율을 얻을 수 있는 것이다.

위에서 언급한 것과 같이 주어진 함수의 결과를 저장하는 장소를 마련해둔 후[3] 이 값을 재활용하는 최적화 기법을 메모이제이션(memoization)이라고 한다.

메모이제이션은 동적계획법에서 빈번하게 사용되므로 동적 계획법에 대해 제대로 배우고 싶다면 필수적으로 배워두워야할 테크닉이다.