dp[i] 상태 정의
인덱스 i까지의 최댓값인지, 금액 i의 최소 개수인지처럼 범위를 포함해 정의합니다.
DP 상태 설계 점검표
DP는 상태 이름, 초기값, 전이 방향이 동시에 맞아야 표가 채워질수록 같은 의미를 유지합니다.
불가능과 0을 구분
아직 만들 수 없는 상태는 큰 값이나 별도 표식으로 두고, 자연스러운 시작점만 0으로 둡니다.
참조가 먼저 계산돼야 한다
이전 칸을 보는지 같은 행을 보는지 정하면 반복문의 순서도 함께 결정됩니다.
제출 전 남길 증거
인접 금지
고른 경우와 건너뛴 경우를 비교해 dp[i]를 갱신합니다.
동전 교환
불가능 상태를 더하지 않도록 초기 큰 값을 따로 둡니다.
메모 방식
탑다운은 호출 중복을 줄이고 바텀업은 채우는 순서를
드러냅니다.