[geek-for-geeks의 원문을 참고하여 작성한 글입니다.]

동적 프로그래밍(DP)은 대개 일반 평문 재귀함수에 대한 최적화 과정입니다. 반복적인 함수 호출에 대해 우리는 DP를 사용하여 최적화 할수 있다. DP는 나중에 필요할 때 다시 연산하지 않기 위해서
subproblem들의 결과값을 간단히 저장합니다. 이 최적화 방식은 지수 다항식으로부터의 시간 복잡도를 줄여줍니다.

동적 프로그래밍 알고리즘의 특성

• 일반적으로 DP는 특정 종류의 문제를 해결하는 데 가장 강력한 기술 중 하나입니다.
• 접근 방식을 공식화하는 우아한 방식과, 매우 간단한 사고 과정, 그리고 매우 쉬운 코딩 파트가 존재합니다.
• 기초적으로, 이 것은 간단한 아이디어인데 주어진 입력과 함께 문제를 푼 이후에는, 미래에 사용할 참조로서 결과를 저장합니다. 그래서 문제를 다시 풀지 않아도 됩니다. 쉽게 말해서 '과거를 기억하세요' :).
• 만약 주어진 문제를 작은 부분 문제로 쪼갤 수 있다면, 그 작은 부분 문제들은 더 작은 부분 문제들로 나눌 수 있습니다. 이 과정에서 부분 문제들에서 겹치는 부분을 볼 수 있는데 이것은 DP에 대해 큰 힌트가 됩니다.
• 추가적으로, 부분 문제에 대한 최적해는 원래 주어진 문제에 대한 최적해로 기여될 수 있습니다.(Optimal Substructure Property 이라고 합니다.)
• 부분 문제의 해는 중복된 계산을 피하기 위해 테이블이나 배열, 그리고 상향식 방식(tabulation)에 저장됩니다.
• 문제의 해는 부분 문제들의 해로부터 구성됩니다.
• DP는 부분 문제의 해를 재귀적으로 찾는 재귀 알고리즘을 사용하거나, 특정한 순서에 따라 부분 문제를 해결하여 해를 찾는 반복 알고리즘을 사용하여 구현될 수 있습니다.

DP는 아래의 원칙에 따라 작동합니다.

• 최적해의 특성 구조화, 즉 해의 수학적 모델 구축
• 최적해의 값을 재귀적으로 정의
• 상향식 접근을 사용하여, 각각의 가능한 부분문제에 대한 최적해의 값을 계산
• 이전의 단계에서 계산된 정보를 사용하여 원래 문제에 대한 최적해 구성

DP의 응용

동적 프로그래밍은 최적해를 구하기 위해 사용됩니다. 이는 아래와 같은 여러 실생활 문제에서 해결하기 위해 사용됩니다.

• change problem 만들기
• Knapsack problem
• 최적의 이진 탐색 트리