큰 문제의 답을 얻으려고 같은 문제이지만 크기가 작은 것들을 먼저 풀어두고, 그 결과를 이용해 큰 문제를 푸는 기법.
겹치는 부분 문제를 적어두기
피보나치 수열이 가장 단순한 예다. 세 번째 원소부터는 바로 앞 두 원소의 합이라, 재귀로 그냥 풀면 fib(3)을 수없이 다시 계산한다. 그 결과를 적어두고 재사용하면 같은 계산을 한 번만 한다.
이 저장소에 정리된 것 중에는 플로이드-워셜이 이 구조를 그대로 쓴다. k번까지 경유해도 되는 최단거리를 k를 늘려가며 채운다. 음수 간선이 있을 때 쓰는 벨만-포드도 2차원 DP다.
분할 정복과 갈리는 지점
분할 정복과 헷갈리기 쉽다. 둘 다 문제를 작게 쪼개지만 부분 문제가 겹치느냐에서 갈린다. 분할 정복은 안 겹치니 각각 따로 풀면 그만이고, 동적 계획법은 겹치니 한 번 푼 것을 저장해두고 재사용한다.
합병 정렬에서 왼쪽 절반과 오른쪽 절반은 서로 무관하다. 피보나치는 그렇지 않다.