DP Restore

DP 공간 최적화와 경로 복원 선택 맵

DP를 압축하면 메모리는 줄지만 어떤 선택으로 답이 나왔는지 복원 정보가 사라질 수 있다.

값·경로 기록 기준

state tradeoff

상태 전체를 남겨 경로 추적이 쉽지만 메모리를 많이 쓴다.

값 계산은 가볍지만 선택 경로가 지워질 수 있다.

선택 여부와 이전 상태를 별도 배열에 기록한다.

디버깅용으로 일부 단계의 상태를 저장한다.

마지막 상태에서 기록을 따라 선택 항목을 복원한다.

문제가 값만 요구하는지 경로도 요구하는지 먼저 본다.

요구사항상태 저장경로 기록복원 검증

복원 정보 해석

공간 최적화는 답만 필요할 때 강하다. 선택 경로가 필요하면 어떤 정보를 버리면 안 되는지 먼저 정해야 한다.