1. 재귀 호출의 각 단계에서 최적해를 만들었던 선택을, 별도의 배열에다 저장. 2. 별도의 재귀 함수를 구현해 이 선택을 따라가며 각 선택지를 저장하거나 출력. 예) LIS에서 LIS 복원하기 : https://sanghoonly.tistory.com/45 -> 1. 최적 선택을 기록하는 choices 배열 생성 후, 2. reconstruct 함수로 choices함수의 값을 이용해 lis 복원.

최적화 문제 : ~의 최댓값을 반환하시오, ~의 최소는 무엇인가 등, 최대/최소/최단거리 등을 도출하는 모든 문제. DP는 태생적으로 최적화 문제를 효율적으로 해결하기 위해 태어남. 주의 : 문제가 최적 부분 구조일때 사용하세요!!!! 최적 부분 구조 (optimal substructure) : 지금까지의 선택과 상관 없이, 각 부분 문제를 최적으로 풀었을 시 전체 문제의 최적해를 도출할 수 있는 구조. ex) 서울에서 부산까지 가는 최단 경로. 최단 경로는 항상 대전을 지남. => 부산 ~ 대전까지의 최단경로 (부분문제 최적해) + 대전 ~ 서울까지 최단경로 (부분문제 최적해) = 부산 ~ 서울까지 최단경로 (전체 최적해) 1. 최적해를 찾는 완전 탐색 알고리즘 설계. 2. 함수 반환 값의 정의 변환 ..

1. 기저 사례를 가장 먼저 처리. 입력 범위 벗어난 경우(nx N 등) 포함 2. cache[]를 전부 -1로 초기화. 3. ret는 cache[a][b]의 참조 변수. 즉 ret의 값이 바뀌면, cache[a][b]의 값도 바뀜. 4. memset()을 이용해 cache를 초기화. 하지만, 굉장히 제한적인 경우에만 쓸것! 레시피의 예. #include // memset을 쓰기 위해 include(백준 등에서 쓰기 위함). int cache[2500][2500]; // 2. 전부 -1로 초기화 해둔다. int dpFunction(int a, int b) { if (...) return ...; // 1. 기저 사례를 가장 먼저 처리. int& ret = cache[a][b]; //..