DP 최적화 적용 기준
공간 압축과 경로 복원은 서로 충돌할 수 있으므로 값만 필요한지 경로도 필요한지 먼저 표시합니다.
정답형 표 만들기
먼저 읽기 쉬운 DP 배열로 작은 테스트를 통과시킵니다.
필요한 행만 보관
이전 행만 참조하면 rolling array나 1차원 배열로 줄입니다.
선택 경로 저장
부모 포인터나 take 배열이 있어야 실제 선택을 되돌릴 수 있습니다.
회귀 검증
압축 전후 결과를 같은 입력에서 비교해 최적화 버그를 잡습니다.