동적 계획법

동적 계획법(Dynamic Programming, DP)은 1957년 Richard Bellman이 다단계 의사결정 문제 해결을 위해 도입한 정확한 최적화 기법입니다. 복잡한 문제를 더 간단하고 중첩된 하위 문제로 분해하고, 각 하위 문제를 한 번만 해결한 후 결과를 저장하여 중복 계산을 피합니다. 최적성 원리(Principle of Optimality)에 근거하여, DP는 중첩된 하위 문제와 최적 부분 구조(optimal substructure)를 보이는 문제에 대해 전역 최적해를 보장합니다.