결정 순간 찾기
각 단계에서 원소 선택, 무게 채우기, 금액 만들기 중 어느 상태를 고르는지 판정한다.
결정이 상태 차원을 만든다기억 정보 줄이기
다음 전이에 꼭 필요한 과거 정보만 상태에 남긴다.
너무 적으면 오답, 너무 많으면 시간 초과다base case 설정
아무것도 선택하지 않은 상태와 불가능 상태의 값을 문제 의미에 맞춘다.
0과 INF와 -INF는 서로 다른 말이다전이 방향 선택
이전 상태에서 현재를 만들지, 현재에서 다음을 밀지 정한다.
1차원 최적화 때 방향이 정답을 바꾼다작은 반례 검증
상태가 부족해 다른 경우를 같은 칸에 합쳐 버리는 입력을 찾아본다.
반례는 상태 설계를 시험한다LIS
마지막 원소 기준
dp[i]를 i에서 끝나는 증가 부분수열 길이로 두면 이전 j<i와
비교한다.
전체 최대는 dp 배열의 최댓값이다
Knapsack
무게 용량 기준
dp[w]는 용량 w에서 얻는 최대 가치를 뜻하고 물건 사용 횟수에
따라 방향이 갈린다.
0/1은 역방향, 무한은 정방향이 자주 쓰인다
Coin
금액 기준
최소 동전 수인지 경우의 수인지에 따라 초기값과 덧셈 방식이
바뀐다.
순열과 조합을 구분한다
Impossible
불가능 상태
도달하지 못한 칸을 전이에 쓰지 않도록 INF나 -INF를 분명히
둔다.
기본 0 초기화가 오답을 만들 수 있다