DP preflight
상태·초기값·전이는 한 칸 계산으로 검증한다
점화식을 쓰기 전에 작은 입력의 한 칸을 손으로 채우면 상태 문장과 전이 후보가 맞는지 바로 드러난다.
base
transition
answer
greedy fail
동전 {1, 3, 4}로 금액 x를 만드는 최소 개수
x
0
1
2
3
4
5
6
dp
0
1
2
1
1
2
2
dp[6] 한 칸 계산
coin 1
dp[5] + 1 = 3
보류
coin 3
dp[3] + 1 = 2
선택
coin 4
dp[2] + 1 = 3
보류
탐욕 반례
4+1+1은 3개, 3+3은 2개
실패
| 점검 | 이 예시의 답 | 실패 신호 |
|---|---|---|
| 상태 문장 | dp[x]는 금액 x를 만드는 최소 동전 수 |
값의 의미 없이 숫자만 채운다. |
| 초기값 | dp[0]=0, 아직 못 만드는 값은 큰 값 |
불가능과 0개를 섞는다. |
| 전이 후보 | 각 동전 c에 대해 dp[x-c]+1을 비교 |
이전 상태를 빠뜨려 탐욕처럼 굳어진다. |