(알고리즘) 최적화 문제 동적계획법

1. 모든 답을 만들어보고  그중 최적해의 점수를 반환하는 완전 탐색 알고리즘을 설계
2. 전체 답의 점수를 반환하는 것이 아니라, 앞으로 남은 선택들에 대해 해당하는 점수 만을 반환하도록 부분문제의 정의를 바꾼다.
3. 재귀호출의 입력에 이전의 선택에 관련된 정보가 있다면 꼭 필요한 것만 남기고 줄입니다. 문제의 최적부분구조가 성립할경우 이전 선택에 관련된 정보를 완전히 없앨 수도 있습니다. 여기서 우리의 목표는  가능한 한 중복되는 부분 문제를 많이 만드는 것입니다.
입력의 종류가 줄어들면 들수록  더 많은 부분 문제가 중복되고 ,따라서 메모제이션을 최대한 활용 할 수 있다.
4. 입력이 배열이거나 문자열인 경우 가능하다면 적절한 변환을 통해 메모제이션 할 수 있도록 합니다.
5. 메모제이션을 적용합니다.


예)
6
1 2
3 7 4
9 4 1 7
2 7 5 9 4

1. 모든 경로를 만들어 보고 전체 합 중 최대치를 반환하는 완전 탐색 알고리즘 path1()을 만듬.
2. path1()이 전체 경로의 최대 합을 반환하는 것이 아니라 (y,x)이후로 만난 숫자들의 최대합만을 반환하도록 바꾼다.
3. 이렇게 반환 값의 정의를 바꿧기 때문에 이전에 한 선택에 대한 정보인 sum을 입력받을 필요가 없어진다. 이 정보를 받을 필요가 없는 것은 문제에 최적 부분 구조가 성립하기 때문입니다.
4. 메모제이션 적용.

---------->>>path(y,x,sum)=현재 위치가 (y,x)이고, 지금까지 만난 수의 합이 sum일 때, 이 경로를 맨 아래줄까지 연장해서 얻을 수 있는 최대합을 반환
path(y,x,sum)=max(path(y+1,x,sum+triangle[y][x]).path(y+1,x+1,sum+triangle[y][x]));

path2(y,x)=(y,x)에서 시작해서 맨 아래줄까지 내려가는 부분경로의 최대합을 반환

path2(y,x)=triangle[y][x]+max(path2(y+1,x),path2(y+1,x+1));