DP 차원 선택 기준

DP 차원 선택 비교판

상태에 필요한 축을 과하게 잡으면 메모리가 늘고, 부족하게 잡으면 전이 정보가 사라집니다.

1차원

한 축의 최선값만 유지

LIS처럼 현재 위치를 끝으로 하는 값이면 이전 위치들을 훑는 1차원 표가 충분합니다.

2차원

두 입력의 접두사 검토

LCS와 편집 거리는 두 문자열의 prefix 길이가 모두 상태에 들어가야 합니다.

압축 여부

이전 행만 필요 시 축소

복원 정보가 필요 없고 참조 범위가 제한적이면 2차원을 1차원으로 낮출 수 있습니다.

제출 전 남길 증거

LIS dp[i]는 i에서 끝나는 증가 부분수열 길이로 읽습니다.
LCS dp[i][j]는 두 접두사의 공통 길이를 뜻합니다.
편집 거리 삽입, 삭제, 교체 세 전이의 최소값을 같은 칸에 모읍니다.