DP Preflight

DP 상태 경계 기준

점화식을 바로 쓰기보다 dp[...]의 의미, 전이가 참조하는 이전 상태, 초기값, 작은 반례를 한 줄씩 확인하면 대부분의 DP 오답이 줄어든다.

1. 상태 문장화 인덱스가 무엇을 뜻하는지 값의 의미부터 고정한다. dp[i]: 0..i에서 가능한 최대 합
2. 전이 후보 분해 선택, 비선택, 불가능 상태를 나누어 이전 상태를 확인한다. take = nums[i] + dp[i - 2]
3. 초기값 고정 빈 입력, 첫 칸, 불가능값을 상태 정의와 같은 의미로 둔다. dp[0] = nums[0], empty = 0
4. 작은 입력 검증 손으로 채울 수 있는 배열에서 각 칸의 의미가 맞는지 본다. [2, 7, 9, 3, 1] → 12
전이 문장 일치 답 위치와 전이 의미가 같은 문장으로 설명된다.
전이 순서 현재 칸이 참조하는 칸은 이미 계산되어 있어야 한다.
위험 신호 같은 dp[i]를 “i 선택”과 “i까지 최적”으로 섞어 읽는다.
반례 우선 빈 입력, 최소 입력, 모두 음수, 불가능 케이스를 먼저 넣는다.
최댓값 DP 각 상태가 부분 구간의 최적값을 담는지 확인한다. max 전이
최소 비용 DP 불가능 상태와 가능한 0 비용 상태를 분리한다. INF 필요
경로 복원 값만 남길지 선택 기록까지 저장할지 미리 결정한다. parent/take