1차원·2차원 DP 기준

상태 의미를 문장으로 쓴다

dp[i]가 i번째까지의 최댓값인지, i를 마지막으로 쓰는 값인지에 따라 전이가 달라진다.

전이가 i-1만 보면 1차원, i와 j 두 선택을 모두 보면 2차원이 자연스럽다.

현재 상태가 참조하는 이전 상태가 이미 채워져 있어야 한다.

한 축 진행 길이, 위치, 용량처럼 하나의 진행 기준만 있으면 후보가 된다.

이전 값 덮어쓰기 주의.

두 선택 기준 문자열 두 개, 물건과 용량, 구간 양끝처럼 두 좌표가 필요하다.

메모리 크기를 먼저 계산한다.

Base

경계값 빈 문자열, 용량 0, 첫 행과 첫 열이 전체 전이를 떠받친다.

초기값이 반례를 많이 잡는다.

Direction

루프 순서 0/1 knapsack처럼 같은 물건 재사용을 막으려면 뒤에서 앞으로 돈다.

문제 모델과 연결된다.

상태 정의 dp 배열 한 칸의 의미를 코드 밖 문장으로 설명할 수 있는가.

초기값 불가능 상태와 0 값을 같은 의미로 섞지 않는가.

메모리 n*m 배열이 제한 안에 들어가는가.

for (auto item : items) {
    for (int w = W; w >= item.weight; --w) {
        dp[w] = std::max(dp[w], dp[w - item.weight] + item.value);
    }
}