[DP] 최적화 DP 레시피

최적화 문제 : ~의 최댓값을 반환하시오, ~의 최소는 무엇인가 등, 최대/최소/최단거리 등을 도출하는 모든 문제. DP는 태생적으로 최적화 문제를 효율적으로 해결하기 위해 태어남.

 

주의 : 문제가 최적 부분 구조일때 사용하세요!!!!

 

최적 부분 구조 (optimal substructure) : 지금까지의 선택과 상관 없이, 각 부분 문제를 최적으로 풀었을 시 전체 문제의 최적해를 도출할 수 있는 구조.

ex) 서울에서 부산까지 가는 최단 경로. 최단 경로는 항상 대전을 지남.

=> 부산 ~ 대전까지의 최단경로 (부분문제 최적해) + 대전 ~ 서울까지 최단경로 (부분문제 최적해) = 부산 ~ 서울까지 최단경로 (전체 최적해)

 

---

 

 

1. 최적해를 찾는 완전 탐색 알고리즘 설계.

 

2. 함수 반환 값의 정의 변환

- 전체 최적해를 반환하는 것이 아닌, 앞으로 남은 선택들에 대한 최적해를 반환하도록 부분 문제 정의를 바꿈.

 

3. 재귀 함수의 파라미터 축소

- 중복되는 부분문제를 더 많이 만들기!

 

4. 메모이제이션 적용.

- 만일 입력이 배열/문자열이라면 => 변환을 통해 메모이제이션 적용.

 

 

---

예시)

최소 합 : https://sanghoonly.tistory.com/43