동적 프로그래밍 vs 분할정복 - joi0104/BOJ GitHub Wiki

공통점

• 두 문제 해결방법 모두 문제를 작은 문제로 나누고 작은 문제의 답을 통해 큰 문제의 답을 구한다.

차이점

• 동적 프로그래밍은 모든 작은 문제를 단 한번만 풀고 이를 어딘가 메모해 놓는다. 그리고 그보다 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 앞서 메모한 작은 문제의 결과값을 이용한다.
• 분할정복은 이와 달리 작은 문제의 답이 필요할 때마다 답을 구한다.
• 즉, 동적 프로그래밍은 작은 문제의 답이 여러번 필요한 경우 분할 정복은 작은 문제의 답이 오직 한번 필요한 경우에 사용한다.