DP 상태 정의
상태 정의가 정확하면 전이와 초기값은 그 정의를 만족하도록 따라옵니다.
부분문제 정답의 의미
dp[i]가 i번째를 포함하는지, i까지 고려한 최적인지 구분합니다.
이미 푼 상태로 계산
선택/미선택, 이전/현재, 위/왼쪽 같은 후보를 비교합니다.
시작 상태
공집합, 첫 원소, 경계 인덱스의 값을 명시합니다.
계산 방향
필요한 선행 상태가 먼저 계산되도록 반복 순서를 정합니다.
상태 정의가 정확하면 전이와 초기값은 그 정의를 만족하도록 따라옵니다.
dp[i]가 i번째를 포함하는지, i까지 고려한 최적인지 구분합니다.
선택/미선택, 이전/현재, 위/왼쪽 같은 후보를 비교합니다.
공집합, 첫 원소, 경계 인덱스의 값을 명시합니다.
필요한 선행 상태가 먼저 계산되도록 반복 순서를 정합니다.