dimension compare

차원은 메모리보다 상태 의미로 먼저 고른다

1D, 2D, parent 배열은 속도 문제가 아니라 “현재 칸을 설명하는 데 필요한 좌표와 복원 정보”가 다르다.

1D 2D parent

문제 신호를 상태 모양으로 바꾸기

1D 한 축으로 진행

금액, 인덱스, 길이처럼 현재 위치 하나만으로 이전 상태를 참조한다.

2D 두 축을 동시에 비교

문자열 두 개의 접두사, 물건 수와 무게처럼 좌표 두 개가 있어야 의미가 고정된다.

parent 선택 경로 복원

최적값뿐 아니라 어떤 선택으로 왔는지 출력해야 하면 parent를 따로 남긴다.

검사 질문	1D	2D	parent
상태 문장	dp[i] = i까지의 최적	dp[i][j] = 두 접두사의 최적	choice[i] = 현재 선택의 출처
전이 참조	이전 몇 칸만 참조	왼쪽, 위, 대각선처럼 주변 칸 참조	값 갱신 때 선택 방향도 기록
압축 가능성	대체로 쉬움	이전 행만 필요하면 가능	경로 출력이 필요하면 압축 주의
대표 반례	복원 요구가 뒤늦게 추가됨	j 순서를 거꾸로 돌려 값 오염	동점 선택 기준이 없어 경로 흔들림

제출 전 기준: 먼저 정답형 상태를 표로 만들고, 그다음 압축한다. 메모리부터 줄이면 초기값과 복원 정보가 사라진다.