compression gate

정답형 상태를 먼저 만들고, 그 다음 압축한다

처음부터 메모리만 보고 압축하면 전이 누락이 생긴다. 먼저 의미가 분명한 상태를 만든 뒤, 참조 범위가 좁을 때만 줄인다.

상태 의미 전이 참조 메모리 압축

압축 전 의사결정

1
상태를 문장화

dp가 무엇의 최적값인지 먼저 고정한다.

2
참조 칸 표시

이전 값, 위/왼쪽/대각선 중 필요한 칸을 표시한다.

3
복원 필요성

경로를 출력해야 하면 parent 또는 전체 테이블이 필요할 수 있다.

4
압축 여부

직전 행만 필요하고 갱신 순서가 안전할 때만 1D로 줄인다.

상황 권장 상태 압축 판단
LIS처럼 이전 인덱스만 본다 dp[i] 1D 그대로 충분
LCS처럼 두 접두사를 비교한다 dp[i][j] 직전 행만 참조하면 row 압축 가능
편집 거리처럼 경로 복원이 필요하다 dp[i][j] + parent 압축하면 복원 정보가 사라질 수 있음