State
부분문제 의미
저장 칸이 어떤 정답을 담는지 먼저 정의한다.
DP는 점화식보다 상태 의미를 먼저 고정한다
`dp[i]`가 무엇을 뜻하는지 한 문장으로 말할 수 있어야 전이와 초기값이 흔들리지 않는다.
Transition
작은 답의 조합
이미 계산된 상태로 현재 값을 만든다.
Base
시작 경계
공집합, 첫 원소 같은 최소 입력의 답을 둔다.
이전 상태
+
현재 선택
→
새 상태