DP (Dynamic Programming)에 대해 배워보겠습니다. 큰 문제를 작은 문제로 나눠서 푸는 방법입니다.

구현 방법 : 모든 작은 문제들을 어디다 저장합니다. (똑같은 계산은 다시 하지 않는다.)

사용 조건 : 작은 문제가 반복해서 일어나고, 같은 문제는 구할 때마다 정답이 같을 때, 사용할 수 있습니다.

Memoization : 아까 언급한 작은 문제를 저장하는 것을 말합니다.

어디서 많이 쓰일까요?

재귀라던가 재귀라던가 재귀라던가…

실제 컴퓨터에 간단한 피보나치 수열을 동작시켰을 때, 인풋하는 n의 값이 조금만 높아져도 계산하는데에 엄청 오래 걸린다. 똑같은 계산을 하고 있으니까 문제가 생기는 것이다.

dp를 이용해 재귀를 표현해보자.

https://www.acmicpc.net/problem/24416