state choice
상태는 “기억해야 할 정보”의 최소 묶음이다
문제 조건을 읽고 현재 선택에 영향을 주는 정보만 상태에 남긴다. 남기지 않아도 되는 정보는 전이에 흡수한다.
index
amount
last
possible
| 문제 신호 | 상태에 남길 정보 | 대표 상태 | 초기 질문 |
|---|---|---|---|
| 마지막 위치까지의 최적값 | 현재 인덱스 | dp[i] |
앞의 결과만 알면 충분한가? |
| 목표 합/금액을 만든다 | 남은 합 또는 금액 | dp[x] |
불가능 상태는 어떤 값인가? |
| 직전 선택이 제약을 만든다 | 마지막 선택 또는 상태 | dp[i][last] |
직전 정보를 빼면 전이가 모호한가? |
| 가능/불가능만 묻는다 | 도달 여부 | can[i] |
최솟값 대신 boolean으로 충분한가? |