quality check
차원 선택은 정확도와 메모리를 함께 결정한다
정답형 상태, 초기값, 전이 방향, 압축 가능성을 분리해 보면 DP 표가 왜 필요한지와 어디까지 줄일 수 있는지가 보인다.
state
base
transition
compress
| 체크 항목 | 통과 기준 | 실패 신호 |
|---|---|---|
| 상태 의미 | dp[i] 또는 dp[i][j]를 한 문장으로 설명한다. | 값은 맞지만 무엇을 뜻하는지 모름 |
| 초기값 | 빈 접두사, 길이 0, 첫 행/열을 먼저 채운다. | i=0 또는 j=0에서 예외 발생 |
| 전이 방향 | 참조 칸이 이미 계산된 뒤에 현재 칸을 채운다. | 아직 계산 안 된 값을 참조 |
| 압축 | 직전 행만 필요하고 복원 정보가 필요 없을 때만 줄인다. | 압축 후 경로 복원이 불가능 |