동적 계획법 Dynamic Programming 또는 DP라고 부른다 1940년대 리차드 벨만이 사용하던 용어이다. 어떤 문제가 주어질 때 본래의 문제를 분석하고 반복되는 연산을 찾아낸다 연산을 기준으로 문제를 작은 문제들로 나눈 다음 각 문제들의 결과값을 기록하며 본래의 문제의 해답을 구하는 방법이다 단계를 구체화하면 다음과 같다 문제 ➡ 점화식 발견 ➡ 작은 문제들로 나누기 ➡ 각 문제의 해답을 기록 ➡ 해답 피보나치 수열 피보나치 수열을 통해 동적계획법을 이해한다 점화식 발견, 연산한 값을 기록하는 것이 dp의 핵심이라 볼 수 있다 피보나치 수열의 0항과 1항은 1이고 n항은 다음과 같이 표현된다 f(n) = f(n-1) + f(n-2) dp를 사용하지 않고 피보나치 특정항을 구해보자 40항을 구하..
