동적 계획법(dynamic programming)은 부분 문제의 해를 결합해 문제를 해결한다. 동적 계획법은 부분 문제가 서로 중복될 때 적용할 수 있다. 동적계획법을 이용하면 모든 부분 문제를 한 번만 풀어 그 해를 테이블에 저장함으로써 각 부분 문제를 풀 때마다 다시 계산하는 일을 피할 수 있다. 동정 계획법 알고리즘을 개발할 때는 다음 4단계를 따른다. 최적해의 구조의 특징을 찾는다. 최적해의 값을 재귀적으로 정의한다. 최적해의 값을 일반적으로 bottom-up 방법으로 계산한다. 계산나된 정보들로부터 최적해를 구성한다. 위의 내용이 Introduction to Alogirhtm 에 수록되어 있는 내용이다. 위 내용을 읽고 생각해보면, 동적 계획법은 각 부분에 대한 값을 계산하고 저장해두며, 필요할..