동적 프로그래밍 DP는 알고리즘 문제 해결에서 효율성을 극대화하는 핵심 전략 중 하나로,
이에 대해서 정리해보자.
동적 프로그래밍이란, 작은 문제의 해답을 저장해두고, 큰 문제를 풀 때 그 값을 재사용하여 중복 계산을 피하려는 최적화 기법이다.
작은 문제 단위로 해결하는 방식!
이에 대표적인 예시로
피보나치 수 구하기가 있다.
$$ f(n) = f(n-1) + f(n-2) $$
위 피보나치 n의 수는 n-1 과 n-2 수를 포함하고 있다.
즉, 큰 문제의 해답이 그보다 작은 문제의 해답이 포함되어 있다.
이런 구조를 최적 부분 구조라고 한다.
이러한 구조는 재귀 호출을 사용해 문제를 해결할 수 있다.