restore + optimize
DP 공간 최적화는 정답형 구현을 먼저 고정한다
값 계산, 압축, 복원, 디버깅을 한 번에 섞지 않고 순서대로 잠그면 메모리를 줄여도 복원 정보를 잃지 않는다.
1 기준값
2 검증
3 압축
4 복원
안전한 설계 순서
1
2D 기준 구현
dp[i][c]와 take[i][c]를 함께 두어 정답 값과 선택 근거를 먼저 맞춘다.
2
작은 입력 검증
손계산 가능한 입력으로 전이식, 초기값, 선택 배열을 같은 표에서 비교한다.
3
압축 후보 분리
값만 필요한 축은 O(C)로 줄이고, 복원에 필요한 정보는 따로 남긴다.
4
복원 경로 확인
최종 상태에서 역추적했을 때 용량과 인덱스가 함께 줄어드는지 확인한다.
| 설계 질문 | 남겨야 할 산출물 | 압축 판단 |
|---|---|---|
| 최종 값만 필요한가 | 값 배열, 순회 방향 | 1D 압축 가능 |
| 선택 경로가 필요한가 | take, parent, tie-break 규칙 |
복원 정보 유지 |
| 디버깅이 필요한가 | 초기 몇 단계 스냅샷 | 작은 입력만 출력 |