다이나믹 프로그래밍(Dynamic Programming)은 작은 문제의 풀이를 통해 큰 문제를 해결하는 방법이다. 분할정복(Divide and Conquer)과의 공통점은 문제를 작게 나눈다는 점이고, 차이점은 작은 문제의 재활용 여부이다.
DP의 풀이방법에는 재귀로 풀이하는 탑다운(Top-down)방식과 반복문으로 풀이하는 (Bottom-up) 방식이 있다. 대부분의 경우 성능은 바텀업 방식이 유리하다. 탑다운방식은 재귀호출로 인해 스택에 한계가 있는 경우 오류가 발생하기 때문이다. 대신 탑다운방식은 코드를 간결하게 만들 수 있다는 장점이 있다.