| 동적프로그래밍 개념 | 동적프로그래밍 사례 | 분할정복과 동적프로그래밍 비교 |
동적 프로그래밍 개념
■ 최적성의 원리는 욕심쟁이 방법에도 적용
■ 동적 프로그래밍 기법 적용 단계
(1) 문제의 특성을 분석하여 최적성의 원리가 적용되는지 확인한다.
(2) 주어진 문제를 소문제로 분해하여 최적해를 제공하는 점화식을 도출한다.
(3) 입력 크기가 작을 때 도출된 점화식의 해를 구한다.
(4) 이 해를 이용하여 점차적으로 입력 크기가 클 때의 점화식의 최적해를 구한다.
