dimension table
문제의 축을 세면 1D와 2D가 갈린다
하나의 진행 축이면 1D, 두 문자열이나 두 수열의 접두사를 동시에 비교하면 2D, 경로가 필요하면 복원 정보까지 둔다.
| 문제 신호 | 상태 차원 | 대표 문제 |
|---|---|---|
| 한 인덱스까지의 최적값 | 1차원 | LIS, 계단, 동전 조합 |
| 두 입력의 접두사 관계 | 2차원 | LCS, 편집 거리 |
| 정답 경로 출력 | parent 추가 | 선택 추적, 문자열 복원 |
| 메모리 상한이 빡빡함 | 압축 검토 | 직전 행만 참조하는 2D DP |