DP design
상태 문장이 곧 표의 한 칸을 정의한다
dp[i]가 무엇을 뜻하는지 먼저 고정하면, 전이는 “현재를 고를지 말지” 같은 선택으로 읽힌다.
skip
take
base
answer
dp[i] = max(dp[i-1], dp[i-2] + a[i])
예시 배열
인접 선택 금지
i
0
1
2
3
4
a[i]
2
7
9
3
1
dp
2
7
11
11
12
| 칸 | 선택지 | 결과 |
|---|---|---|
| i=2 | skip=7, take=2+9 |
take 11 |
| i=3 | skip=11, take=7+3 |
skip 11 |
| i=4 | skip=11, take=11+1 |
take 12 |
| 설계 질문 | 이 예시의 답 | 틀리면 생기는 문제 |
|---|---|---|
| 상태 의미 | i까지 봤을 때 최대 합 |
정답 위치를 잘못 읽음 |
| 초기값 | dp[0]=2, dp[1]=7 |
전이 시작점이 흔들림 |
| 전이 후보 | 현재를 버리거나, 현재를 고르고 두 칸 전과 합침 | 인접 금지 조건을 깨뜨림 |