동적 프로그래밍 (Dynamic Programming)

다이나믹 프로그래밍이란 하나의 문제는 단 한 번만 풀도록 하는 알고리즘

크고 어려운 문제가 있으면, 그것을 먼제 잘게 나누어 해결한 뒤에 처리하여 나중에 전체의 답을 구하는 것

 

Memoization이 사용됨

이미 계산한 결과는 배열에 저장함으로써 나중에 동일한 계산을 해야할 때는 저장된 값을 단순히 반환하기만 하면 됨

 

 

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다

-> 이 두 가정이 모두 성립하면 다이나믹 프로그래밍 사용 가능