상태 정의
dp[i]를 "i번째까지 고려했을 때의 최소 비용"처럼 인덱스와 포함 범위까지 문장으로 고정합니다.
DP Design
DP 점화식 설계 맵
DP는 상태 의미를 고정하고 점화식, base case, 채우는 순서를 맞춘 뒤 테이블 크기로 시간·공간 복잡도를 계산합니다.
상태·전이·순서·복잡도
recurrence전이식
예: dp[i] = min(dp[i-1] + cost1, dp[i-2] + cost2)처럼 이전 상태와 선택 비용을 함께 씁니다.
초기값
dp[0], dp[1] 같은 base case가 없으면 음수 인덱스나 미초기화 값을 참조합니다.
테이블 순서와 비용
전이가 참조하는 방향대로 테이블을 채우고, 상태 수와 전이 수를 곱해 O(N), O(NM)처럼 계산합니다.
문제 조건staterecurrencebase caseorder/answer
DP 오답은 대개 상태 정의 누락, base case 부족, 채우는 순서 오류, 답 위치 착각에서 납니다. 표를 채우기 전 네 항목을 먼저 씁니다.