| 동적프로그래밍 개념 | 동적프로그래밍 사례 | 분할정복과 동적프로그래밍 비교 |

■ 동적 프로그래밍(dynamic programming) 개념

• 주어진 문제를 여러 개의 소문제로 분할하여 각 소문제의 해결안을 바탕으로 주어진 문제를 해결하는 기법이다.
• 이때 각 소문제는 다시 또 여러 개의 소문제로 분할될 수 있다.
• 각 소문제는 원래 주어진 문제와 동일한 문제이지만 입력 크기가 작다.
• 따라서 소문제를 반복하여 분할하면 결국 입력의 크기가 아주 작은 단순한 문제가 되어 쉽게 그 문제를 해결할 수 있다.
• 이러한 소문제의 해를 표 형식으로 저장해놓고 이를 이용하여 입력 크기가 보다 큰 원래의 문제를 점진적으로 해결해 나간다.

■ 최적성의 원리

• 정의 : 주어진 문제에 대한 최적해가 소문제에 대한 최적해로 구성되는 경우
            그 문제는 최적성의 원리가 성립한다.
• 동적 프로그래밍은 최소치 또는 최대치를 구하는 최적화 문제에 적용된다.
• 최적화 문제의 최적해는 여러 개가 있을 수 있지만 그 중의 어느 하나를 구하면 되며 최적해는 기본적인 소문제의 최적해로부터 보다 큰 크기의 소문제의 최적해를 구하는 과정을 거친다.
• 동적 프로그래밍을 적용할 수 있으려면 최적성의 원리가 성립하여야 한다.
• 어떤 문제에 최적성의 원리가 적용된다면 소문제에 대한 최적해를 이용하여 더 큰 크기에 대한 최적해를 구하는 순환적 관계, 즉 점화식을 도출할 수 있다. 따라서 문제의 크기가 작은 경우의 점화식에 대한 해를 구한 다음 거꾸로 점점 크기가 큰 문제의 해를 구할 수 있다.