dp[0]은 “0번째까지의 최대”라서 3이고, dp[1]은 max(3, 2)다.
state sentence
상태 문장은 표의 첫 칸과 전이 후보를 동시에 정한다
상태 의미가 정해지면 초기값, 선택 후보, 답 위치가 같은 표 안에서 검증되어야 한다.
base
skip
take
dp[i] = 0..i번째 집까지 봤을 때, 인접한 집을 고르지 않고 얻는 최대 금액
입력 [3, 2, 5, 10, 7]로 채운 DP 표
| i | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 값 | 3 | 2 | 5 | 10 | 7 |
| skip | - | 3 | 3 | 8 | 13 |
| take | 3 | 2 | 8 | 13 | 15 |
| dp | 3 | 3 | 8 | 13 | 15 |
dp[i]는 `skip = dp[i-1]`과 `take = dp[i-2] + value[i]` 중 큰 값이다.
상태가 “i번째까지”이므로 답은 마지막 칸 dp[4] = 15에 남는다.