DP 차원 결정 기준

결정 변수 찾기

문제의 답이 위치, 개수, 남은 용량, 마지막 선택 중 무엇에 따라 달라지는지 고른다.

축 후보

dp[i] 또는 dp[i][j]가 어떤 이전 칸을 읽는지 화살표로 확인한다.

전이 방향

같은 행의 이전 값이 필요한지, 이전 행만 필요한지에 따라 증가·감소 순회를 정한다.

중복 사용 방지

최댓값만 필요한지 선택 경로까지 필요한지에 따라 부모 정보를 남길지 결정한다.

값과 경로 분리

1D 가능

직전 값 또는 한 축만 필요 계단, 피보나치, 일차원 누적처럼 현재 인덱스만으로 충분하다.

공간 O(n) 이하

2D 필요

두 조건이 독립적으로 답을 바꿈 i번째 물건과 남은 용량처럼 상태를 둘 다 알아야 한다.

축 제거 전 의존성 확인

압축 가능

이전 행만 참조 현재 행 계산이 이전 행에만 의존하면 1D로 줄일 수 있다.

순회 방향이 핵심

압축 불가

복원 또는 여러 행 참조 경로 출력이나 긴 구간 의존성이 있으면 정보를 버리면 안 된다.

부모 배열 유지

초기값 불가능한 상태는 0이 아니라 음의 무한대나 별도 표시가 필요할 수 있다.

갱신 순서 0/1 선택은 보통 역순, 무한 선택은 정순 갱신이 맞는지 확인한다.

메모리 n과 m을 곱한 크기가 제한을 넘으면 압축 또는 다른 상태가 필요하다.

0/1 knapsack: for w from W down to weight
unbounded:      for w from weight up to W
path restore:   keep parent or decision table