[알고리즘] 동적 계획법 (Dynamic Programming)

동적 계획법이란?

 - 큰 문제를 작게 최소화해서 푸는 알고리즘이다.

 - 부분 문제를 해결한 결과를 이용하여 전체 문제를 해결한다.

 - 시간 복잡도를 줄이기 위해 공간을 늘린다.

 - 즉, DP는 이전 정보를 가지고 있어서 공간을 많이 사용한다.

풀이 순서

 1. 구하고자 하는 큰 문제에서 작은 부분 문제를 정의한다.

 2. 가장 작은 부분 문제부터 풀어 문제에 대한 점화식을 구한다.

     - 가장 작은 부분 문제의 답을 저장한다.

     - 부분 문제들의 해를 이용하여 차례로 더 큰 상위 문제의 답을 구한다.

 3. 문제를 해결한다.

 

주의할 점

 - 초기화