동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 해결하기 위한 알고리즘 기법으로, 문제를 작은 하위 문제들로 나누고, 각 하위 문제의 해를 저장하여 필요할 때 다시 사용함으로써 전체 문제를 효율적으로 해결하는 방법이다. DP는 특히 중복되는 하위 문제(subproblems)를 가진 문제에서 매우 유용하다. 즉 앞에서 설명한 분할 계획을 조금 더 효율적으로 할 수 있는 것이다. 동적 계획법의 핵심 개념최적 부분 구조: 문제의 최적해가 그 하위 문제들의 최적해로 구성될 수 있어야 한다.예를 들어, 최단 경로 문제에서는 전체 경로의 최단 거리는 경로의 부분 문제에서도 항상 최단 거리로 구성될 수 있다.중복되는 하위 문제: 동일한 하위 문제가 여러 번 반복해서 계산되는 경우가 있어야 ..
