State Design
DP 상태 설계 점검 기준
상태, 초기값, 전이 순서, 답 위치를 분리하면 테이블을 채우는 방향이 선명해집니다. 상태 문장이 흐리면 전이식도 맞아 보이는 우연에 기대게 됩니다.
상태
dp[i]가 “i번째까지 봤을 때의 무엇”인지, 포함/미포함 기준까지 문장으로 적습니다.
초기값
빈 입력, 첫 원소, 불가능 상태를 나눠 두어 전이식이 음수 인덱스나 쓰레기 값을 읽지 않게 합니다.
전이
이전 상태만 읽고 압축 순회 방향을 맞춥니다.
답
반환할 칸/최댓값 기준을 문제 문장과 맞춥니다.