Dynamic Programming

동적계획법이란

두 가지 조건을 포함해서 복잡한 문제를 보다 단순한 부분 문제로 나누어 해결하는 방법입니다.

1. 부분문제들의 최적해가 전체의 최적해를 이룹니다.

2. 동일한 부분문제들이 여러번 발생합니다.

   • 조건이 충족되지 않으면 분할&정복 문제라고 합니다.

동적계획법의 핵심

중복되는 연산을 미리 캐싱해 두고, 중복 연산이 발생할 때 마다 참조하여 연산을 줄입니다. 즉, 공간과 시간복잡도를 trade한 대표적인 방법이라고 볼 수 있습니다.