다이나믹 프로그래밍이란, 큰 문제를 작은 문제로 나누어 푸는 방법을 말한다. 이때, 작은 문제들을 풀어나가면서 중복되는 문제들이 발생하는데, 이를 저장해두었다가 재활용하는 방식으로 효율적으로 문제를 해결한다.
적용 가능한 문제들은 다음과 같다.
- problem이 더 작은 subproblem으로 나눌 수 있다.
- 나눠진 subproblem으로 더 큰 문제를 해결할 수 있다.
- subproblem의 해결방법이 항상 같다.
다이나믹 프로그래밍은 크게 top-down 방식과 bottom-up 방식으로 나뉜다.
- top-down: 큰 문제를 작은 문제로 나누어 푸는 방식. 재귀함수를 이용하여 작은 문제를 풀어나간다.
- 문제의 크기가 커지면 콜스택이 커져서 동작하지 않을 수 있다.
- bottom-up: 작은 문제부터 풀어나가는 방식. 반복문을 이용하여 작은 문제를 풀어나간다.