1차원 압축 후보
최종 최댓값이나 최소 비용만 묻는다면 이전 행 전체를 들고 있을 필요가 줄어듭니다.
복원 요구별 DP 저장 전략
값만 구하는 DP와 선택 경로를 되살리는 DP는 저장해야 할 정보가 다르므로 최적화 전에 출력 요구를 먼저 읽어야 합니다.
부모 정보가 필요
무엇을 골랐는지 출력해야 하면 값 테이블과 별도로 선택 방향을 남겨야 합니다.
스냅샷으로 전이 확인
중간 행을 출력하면 순회 방향 오류와 덮어쓰기 실수를 빠르게 찾을 수 있습니다.
제출 전 남길 증거
압축 전
참조하는 칸이 덮이기 전인지 반복 방향을 먼저 확인합니다.
복원 단계
마지막 칸에서 거꾸로 이동할 수 있는 단서를 저장합니다.
디버깅 로그
입력 하나씩 늘리며 dp 행이 예상대로 변하는지 비교합니다.