다이나믹 프로그래밍 (Dynamic Programming) 직역하면 동적 프로그래밍으로 불리는 이 프로그래밍 방법은 큰 문제를 작은 부분으로 나누어 작은 부분들을 이용해 큰 문제를 해결하는 기법입니다. 이와 대조되는 분할 정복 알고리즘 역시 큰 문제를 한번에 처리하기에 연산 수가 크고 복잡하여 큰 문제를 작은 부분으로 나누는 기법입니다. 방법은 유사하지만 동적 프로그래밍은 작은 부분들을 다시 반복하여 연산하지 않는다는 차이점이 존재합니다. 즉, 큰 문제들을 작은 문제들로 나누는 과정은 동일하지만 분할 정복은 작은 문제들을 다시 연산하고 다이나믹 프로그래밍은 미리 연산된 결괏값을 재사용합니다. 다이나믹 프로그래밍에서 모든 작은 문제들은 반드시 한번만 사용하게 됩니다. 따라서 연산이 끝난 문제들은 어딘가에 ..