DP 상태에서 정보를 하나 줄이려 합니다. 같은 상태로 합친 두 과거가 미래 전이를 다르게 만드는지 어떻게 확인하나요?

두 과거를 같은 DP 상태로 합쳐도 이후 가능한 선택과 비용이 같아야 합니다. 남은 개수·마지막 선택·사용한 자원에 따라 미래가 달라지면 그 정보는 상태에 남겨야 합니다.

동전을 무한히 쓸 때 금액만으로 충분할 수 있지만 각 동전 개수 제한이 있으면 같은 금액도 남은 재고가 다릅니다. 작은 완전 탐색 반례로 잘못된 상태 축약을 찾습니다. 상태 수 절감과 정확성·역추적 정보를 함께 평가합니다.