동적 계획법은 반복되는 부분 문제의 결과를 저장하고 의존 관계에 따라 계산하여 전체 문제를 푸는 방법이다.
원리
상태의 의미, 상태 사이의 전이, 초기값과 계산 순서를 정한다. 보통 상태 수와 상태 하나의 전이 비용을 곱해 시간 복잡도를 분석한다.
예시
계단을 한 번에 1칸 또는 2칸 오르는 경우의 수는 직전 두 상태의 합으로 계산할 수 있다. 같은 높이의 경우의 수를 매번 재귀로 다시 구하지 않는다.
주의할 점
상태에 필요한 정보를 빼면 서로 다른 상황을 같은 것으로 취급하게 된다. 최적값만 저장하는 것과 실제 선택 경로까지 복원하는 것은 별도 설계다.