Dynamic Programming이란?

Dynamic Programming

복잡한 문제를 작은 하위 문제로 나누어 해결하고, 각 하위 문제의 해답을 저장하여 중복 계산을 피하는 방식으로 전체 문제의 해답을 찾는 알고리즘 설계 기법

적용 가능한 문제

• 최적 부분 구조: 큰 문제의 최적 해답이 그 문제의 하위 문제들의 최적 해답으로부터 구성될 수 있는 경우
• 중복되는 하위 문제: 문제를 해결하는 과정에서 동일한 하위 문제가 반복적으로 발생하는 경우