DP란?
- DP란 메모리 [ex) 데이터를 담아놓을 수 있는 변수 등]에 저장하여 수행시간을 비약적으로 향상시키는 방법
- 연속적인 연산에 있어서 이미 계산된 결과를 메모리에 저장하여 다시 계산하지 않고 활용
- Top-Down, Bottom-Up 방식이 있음
DP 알고리즘을 사용해야 하는 경우
- 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제를 모아서 큰 문제를 해결할 수 있는 경우
- 중복되는 부분 문제 : 동일한 문제를 반복적으로 해결해야 하는 경우
DP 알고리즘을 사용해야 할 경우 가장 먼저 해야할 것
제시된 문제에서 문제 해결을 위해 필요한 '일정한 규칙'을 찾고 이를 위한 점화식을 도출
