DP 공간 최적화와 경로 복원

참조 범위 확인

현재 상태가 바로 이전 행만 참조하면 rolling array가 가능하고, 더 오래된 값이 필요하면 어렵다.

1차원 압축에서 앞에서 돌면 같은 단계 값을 다시 써 버릴 수 있다.

최댓값만 남기면 어떤 선택을 했는지 알 수 없으므로 parent나 choice 배열을 별도로 저장한다.

Rolling

행 교체 i-1 행만 필요하면 두 행 또는 한 행으로 줄일 수 있다.

인덱스 parity를 조심한다.

역방향 반복

재사용 차단 0/1 선택에서는 같은 물건을 한 번만 쓰기 위해 뒤에서 돈다.

unbounded 문제는 방향이 달라진다.

Parent

경로 복원 선택한 이전 좌표를 기록해 답을 역추적한다.

메모리와 출력 요구를 맞춘다.

표 점검

작은 입력 검산 n=3 정도의 표를 손으로 채우면 초기값과 방향 오류가 보인다.

디버깅 효율이 높다.

덮어쓰기 압축된 배열이 아직 필요한 이전 값을 먼저 덮지 않는가.

복원 요구 문제가 값만 요구하는지 선택 목록도 요구하는지 확인했는가.

불가능 상태 -INF, INF, false 같은 초기 상태가 전이에서 오염되지 않는가.

// before optimizing memory:
// print dp table for n <= 4
// compare each transition with handwritten table