state design
DP 상태는 네 가지 기준을 동시에 통과해야 한다
상태, 초기값, 전이 순서, 답 위치를 분리해서 점검하면 점화식 오류를 초기에 잡을 수 있다.
state
base
transition
answer
| 체크 항목 | 통과 기준 | 실패 신호 |
|---|---|---|
| 상태 | dp[i]가 무엇을 보장하는지 한 문장으로 말한다. |
전이를 설명할 때 상태 의미가 바뀐다. |
| 초기값 | 빈 입력, 첫 원소, 불가능 상태를 나눠 둔다. | 첫 칸이나 불가능 입력에서 예외 처리만 늘어난다. |
| 전이 | 현재 칸보다 먼저 계산된 값만 참조한다. | 아직 채우지 않은 칸을 읽는다. |
| 답 | 마지막 칸, 전체 최댓값, 특정 상태 중 하나로 고정한다. | 계산은 맞는데 출력 위치가 흔들린다. |