상태 문장
인덱스가 가리키는 범위와 선택 조건을 한 문장으로 고정합니다.
DP 상태 먼저
DP 상태 문장과 초기값
인접 금지 최대 합, 동전 교환, 피보나치는 모두 상태 의미가 맞아야 전이 순서와 불가능 값도 안전하게 정해집니다.
dp[i]
0..i 구간에서 조건을 만족하는 최적값
전이 후보
선택/비선택, 이전 금액, 이전 두 항처럼 의존 상태를 분리합니다.
초기값
공집합, 첫 원소, 불가능 상태를 상태 의미에 맞춰 채웁니다.