choice map

값, 경로, 로그 중 무엇을 남길지 먼저 고른다

공간 최적화의 핵심은 배열을 줄이는 것이 아니라, 줄여도 되는 정보와 남겨야 할 정보를 분리하는 것이다.

value path debug
상황 추천 구조 반드시 보존할 것 주의점
최종 값만 필요 dp[c] 1차원 역순/정순 순회 방향 복원 질문이 들어오면 정보가 부족하다.
선택 경로 필요 2D dp + take 아이템 선택 여부, tie-break 메모리를 줄이기 전에 경로 저장 방식을 확정한다.
메모리 제한 빡빡 값은 압축, 경로는 parent 이전 상태 포인터 압축 배열만으로는 역추적이 깨질 수 있다.
전이식 의심 작은 입력 스냅샷 초기 몇 단계 표 대형 로그는 시간 초과와 오진을 만든다.