[DP] 최적화 문제 실제 답 계산 레시피

 

1. 재귀 호출의 각 단계에서 최적해를 만들었던 선택을, 별도의 배열에다 저장.

 

2. 별도의 재귀 함수를 구현해 이 선택을 따라가며 각 선택지를 저장하거나 출력.

 

---

 

예)

LIS에서 LIS 복원하기 : https://sanghoonly.tistory.com/45

->

1. 최적 선택을 기록하는 choices 배열 생성 후, 

2. reconstruct 함수로 choices함수의 값을 이용해 lis 복원.