동적 계획법의 접근 방식 1단계: 동적 계획법 필요조건 분석하기 부분집합의 합과 같은 문제에 직면하게 되면먼저 이 문제를 동적 계획법으로 해결할 수 있는지를 확인해야 한다.일반적으로 주어진 문제가 다음 속성을 가지고 있다면 동적 계획법으로 해결할 수 있다. 중복되는 부분 문제 : 일반적인 분할 정복 기법과 마찬가지로,최종해(final solution)는 여러 개의 부분 문제 조합으로 표현될 수 있어야 한다.그러나 분할 정복과는 달리 특정 부분 문제가 여러번 발생할 수 있다.최적 부분 구조 : 주어진 문제에 대한 최적해(optimal solution)는부분 문제의 최적해로부터 생성될 수 있다. 위 그림을 보면 크기가 n인 부분집합은 크기가 n - 1인 부분집합에 새로운 원소 하나를 추가하여 만들 수 있다..