최적 부분 구조란, " 부분 문제의 답을 이용해서 기존 문제의 답을 구할 수 있는 구조"를 가진 구조이다. 예를 들어, 총 5개의 새콤달콤을 팔려는 영희가, 1개에는 100원, 2개에는 400원, 3개에는 800원, 4개에는 900원 , 5개에는 1000원에 팔고자 하고, 이 수익을 최대화 하는 전략을 고민하는 문제가 있다고 하면, 5개를 갖고 최대 수익을 내는 방법 1. 4개를 갖고 최대 수익을 내는 방법 + 1개를 갖고 최대 수익을 내는 방법 2. 3개를 갖고 최대 수익을 내는 방법 + 2개를 갖고 최대 수익을 내는 방법 3. 5개를 한명에게 팔았을 때의 수익 과 같이 구분 지을 수 있다. 3번의 경우에는 심플하지만 1, 2번의 경우 결국 4개를 갖고 최대 수익을 내는 방법은 2개, 2개씩 혹은 3개..
