정보량을 세고, 축을 고른 뒤, 압축 가능성을 따진다
상태 차원은 필요한 독립 정보의 수다. 먼저 정답형 상태를 만들고, 의존 방향이 보존될 때만 메모리를 줄인다.
정보량정답에 필요한 값 세기
축 선택독립 변수만 상태화
1DLIS, 금액 누적
2DLCS, 편집 거리
압축순회 방향 확인
반례기저와 덮어쓰기 검사
상태 축 수 결정
state axis문제 단서
상태 후보
대표 문제
현재 위치 하나가 이전 선택을 요약한다
dp[i]: i에서 끝나는 최적값LIS, 최대 부분합, 계단형 누적
두 입력을 동시에 한 칸씩 비교한다
dp[i][j]: 두 접두사의 최적값LCS, 편집 거리, 문자열 정렬
용량, 개수, 마지막 선택이 함께 필요하다
축 추가 전 중복 정보인지 먼저 제거
배낭, 구간 DP, 상태 압축 DP
값 비교 조건이 전이 방향을 제한한다
nums[j] < nums[i] 같은 조건 포함순회 순서가 불변식을 만든다
반례 검증 순서
test set
빈 입력초기 행/열,
n=0
완전 불일치전이가 0 또는 삭제 비용 유지
완전 일치대각선 증가와 비용 0 확인
길이 극단한쪽만 긴 경우 오프셋 검사