DP Master

상태 정의의 네 요소

dp[i]처럼 기호만 적으면 의미가 부족하다. 상태 문장에는 처리한 범위, 마지막 위치나 조건, 저장하는 값, 최적화 방향이 들어가야 한다.

• 모호함: dp[i] = i까지의 답
• 명확함: dp[i] = 앞의 i개 원소를 처리했을 때 얻는 최대 점수
• 끝점 상태: dp[i] = i번째 원소를 반드시 선택하고 끝나는 최대 점수

두 번째와 세 번째 정의는 비슷해 보이지만 정답을 읽는 위치가 다르다. 끝점 상태라면 전체 정답은 보통 max(dp[i])다.

상태를 줄이는 기준

서로 다른 과거 두 개가 앞으로 가능한 선택과 이후 비용이 완전히 같다면 하나의 상태로 합칠 수 있다. 반대로 마지막 색, 사용한 특별 행동, 연속 선택 길이가 미래를 바꾸면 반드시 별도 축으로 남긴다.

초기 상태는 증명의 시작점

초기 상태는 단순한 코딩 편의가 아니라 점화식이 참이기 시작하는 근거다. 경우의 수에서는 아무것도 고르지 않는 빈 구성을 dp[0]=1로 두는 경우가 많다. 이 1이 이후 첫 선택을 만드는 출발점이 된다.

최솟값 DP는 도달 불가능 상태를 INF로 두고, INF + cost가 overflow하지 않도록 갱신 전에 도달 여부를 확인한다. 최댓값 문제에 음수가 있다면 0을 불가능 표시로 쓰면 존재하지 않는 빈 경로가 실제 답보다 커질 수 있다.

제출 전 확인

• 빈 입력이나 길이 1 상태가 점화식과 일치하는가?
• 정확히 합을 만들어야 하는 상태를 0으로 초기화하지 않았는가?
• long long 범위에서 INF와 비용의 합이 안전한가?
• Top-down의 미방문 표시와 실제 정답 값이 충돌하지 않는가?

과거 전체 대신 경계만 기억하기

배열을 왼쪽부터 처리할 때 모든 선택 기록을 저장할 필요는 없다. 다음 선택을 결정하는 데 필요한 정보만 last, used, consecutive 같은 작은 축으로 남긴다.

예를 들어 같은 행동을 세 번 연속 할 수 없다면 과거 전체가 아니라 마지막 행동과 현재 연속 길이 0, 1, 2만 필요하다. 특별 행동을 최대 한 번 쓸 수 있다면 used는 0 또는 1이다. 이처럼 상태 수가 입력 크기와 무관한 상수이면 각 위치를 한 번 순회하는 전체 복잡도도 O(N)이다.

핵심 질문: 다음 위치의 가능한 선택과 비용을 결정하려면 과거에서 무엇만 기억하면 되는가?

현재 원소를 선택하는 경우와 선택하지 않는 경우를 분리한다. House Robber처럼 인접 원소를 함께 선택할 수 없다면 다음 두 관점이 모두 가능하다.

• dp[i] = max(dp[i-1], dp[i-2] + value[i])
• dp[i][taken] = i까지 처리했고 i의 선택 여부가 taken일 때의 최댓값

첫 표현은 상태를 더 압축했고, 두 번째 표현은 전이의 의미를 더 직접적으로 보여준다. 연속 선택 개수가 2까지 허용되는 식으로 조건이 확장되면 consecutive 축을 추가하는 편이 안전하다.

선택하지 않는 전이를 빼먹으면 이전 최적 상태를 그대로 유지할 수 없고, 반대로 선택 전이에서 제한을 확인하지 않으면 금지된 조합이 답에 포함된다.

dp[i][last]는 앞의 i개를 처리했고 마지막 상태가 last일 때의 최적값이다. RGB거리에서는 last가 세 색이고, 비행 모드에서는 일반과 터보처럼 고정된 모드가 된다.

전이는 현재 상태로 들어올 수 있는 이전 상태만 확인한다.

for (int now = 0; now < STATE; ++now)
    for (int prev = 0; prev < STATE; ++prev)
        if (allowed(prev, now)) relax(dp[i][now], dp[i-1][prev]);

STATE가 3이나 5처럼 고정된 상수라면 O(N·STATE²)는 O(N)이다. 다만 입력으로 K가 주어져 상태가 0..K로 늘어나면 더 이상 상수 상태 DP가 아니다.

곱셈처럼 음수가 부호를 뒤집는 문제에서는 지금까지의 최댓값만 저장하면 정보가 부족하다. 아주 작은 음수 값이 다음 음수와 곱해져 가장 큰 양수가 될 수 있기 때문이다.

각 위치에서 다음 세 후보를 비교한다.

1. 현재 값 x에서 새 구간을 시작한다.
2. 이전 최댓값에 x를 곱해 이어 붙인다.
3. 이전 최솟값에 x를 곱해 이어 붙인다.

nextMax = max(x, prevMax*x, prevMin*x), nextMin = min(x, prevMax*x, prevMin*x)로 함께 갱신한다. 두 값을 순서대로 덮어쓰지 말고 이전 값을 보존한 뒤 동시에 계산해야 한다.

dp[i]를 계산할 때 i-1만 보면 되는지 먼저 확인한다. 마지막으로 선택한 위치나 마지막 분할점이 답을 바꾼다면 j<i인 후보를 탐색해야 한다.

for (int i = 0; i < n; ++i)
    for (int j = 0; j < i; ++j)
        if (can_move(j, i)) dp[i] = max(dp[i], dp[j] + gain(i));

이중 반복문을 쓰기 전에 후보 j가 무엇을 뜻하는지와 cost(j, i)가 어떤 마지막 행동을 나타내는지 문장으로 적는다.

스스로 설명해 보기

• j가 마지막 위치인지, 분할점인지, 이전 선택인지 말할 수 있는가?
• 두 번째 상태 축의 범위가 상수인지 입력에 따라 커지는지 계산했는가?
• 복원이 필요할 때 어떤 이전 상태를 parent에 기록할지 정했는가?

디버깅 기준: 작은 입력의 모든 후보를 손으로 적고 DP가 같은 후보를 확인하는지 비교한다.

dp[i][j]의 두 축은 각각 무엇을 처리했는지 명확해야 한다. 두 문자열의 앞부분이라면 (i, j)는 두 prefix의 길이이고, 정확히 j개를 골랐다면 두 번째 축은 선택 개수다.

최적값뿐 아니라 실제 경로가 필요하면 갱신할 때 선택한 이전 상태를 parent[state]에 기록한다. 동률 처리 규칙도 복원 결과에 영향을 준다.

구현 순서

1. 모든 상태를 불가능 값으로 초기화한다.
2. 현재 상태에 들어올 수 있는 이전 후보만 순회한다.
3. 값이 좋아질 때 parent도 같은 순간에 갱신한다.
4. 마지막 상태에서 parent를 역추적하고 결과 순서를 뒤집는다.

배낭 DP는 보통 물건 선택과 제한 자원을 함께 관리한다. dp[w]를 정확히 무게 w를 사용한 최적값으로 둘지, w 이하를 사용한 최적값으로 둘지 먼저 결정한다.

0/1 배낭은 한 물건을 같은 단계에서 다시 쓰지 않도록 용량을 큰 쪽에서 작은 쪽으로 갱신한다. 무한 배낭은 작은 쪽에서 큰 쪽으로 갱신해 현재 물건을 다시 사용할 수 있게 한다.

스스로 설명해 보기

• 각 물건을 0번, 1번, 여러 번, 최대 c번 중 몇 번 쓸 수 있는가?
• dp[w]는 정확히 w를 쓴 상태인가, w 이하를 쓴 상태인가?
• 1차원 압축에서 반복 방향이 사용 횟수 조건과 일치하는가?

디버깅 기준: 물건 하나만 있는 입력으로 같은 물건이 의도보다 많이 사용되는지 확인한다.

정확히 합 W를 만들어야 한다면 dp[0]만 도달 가능하게 초기화하고 나머지는 불가능 상태로 둔다. 용량 W 이하의 최대 가치라면 빈 선택의 가치 0이 모든 용량에서 유효할 수 있다.

가치 기준 배낭, 정확히 K개 선택, 두 자원 제한도 같은 원리로 미래에 필요한 자원을 상태 축에 추가한 것이다.

구현 순서

먼저 2차원 DP로 물건 단계가 분리되는지 확인한 뒤 1차원으로 압축한다. 압축할 때는 현재 단계 값을 같은 단계에서 다시 읽어도 되는지 판단해 반복 방향을 정한다. 정확한 합 문제라면 마지막에 dp[W]의 도달 가능 여부도 별도로 확인한다.

dp[i][j]는 보통 첫 번째 수열의 앞 i개와 두 번째 수열의 앞 j개를 처리한 답이다. 마지막 원소를 서로 매칭하거나, 한쪽 원소를 버리거나, 양쪽을 모두 처리하는 선택으로 전이가 만들어진다.

LCS, 편집 거리, LCIS는 표의 모양은 비슷하지만 상태의 값과 허용하는 마지막 행동이 다르다.

스스로 설명해 보기

• dp[i][j]의 i와 j가 각각 어느 prefix를 뜻하는가?
• 두 원소를 매칭할 때와 한쪽을 버릴 때의 전이를 모두 적었는가?
• 길이, 개수, 실제 수열 중 무엇을 출력해야 하는가?

디버깅 기준: 빈 문자열, 같은 문자열, 공통 문자가 없는 문자열을 각각 확인한다.

최적 길이만 구할 때는 max로 충분하지만 개수를 세려면 같은 결과가 여러 전이에서 중복 집계되는지 확인해야 한다. 실제 답을 출력하려면 parent 또는 역추적 가능한 DP 표가 필요하다.

LIS의 tails 배열은 길이를 빠르게 구하지만 실제 LIS 그 자체는 아니다. 복원하려면 각 원소의 이전 인덱스를 별도로 기록한다.

구현 순서

첫 행과 첫 열을 빈 prefix의 답으로 초기화한다. 이후 마지막 두 원소가 같은 경우와 다른 경우를 분리해 표를 채운다. 복원이 필요하면 답의 끝점에서 시작해 값이 만들어진 방향을 거꾸로 따라가며 선택한 원소를 모은다.

기본 격자 DP는 dp[r][c]로 충분하지만, 직전에 이동한 방향이나 벽 제거 사용 여부가 다음 이동을 바꾸면 dp[r][c][direction], dp[r][c][used]가 필요하다.

각 축은 미래 전이에 필요한 정보여야 한다. 단순히 차원을 늘리는 것이 아니라 서로 다른 미래를 갖는 상태만 분리한다.

스스로 설명해 보기

• 위치 외에 방향이나 자원 사용 여부가 미래 이동을 바꾸는가?
• dp[l][r]이 참조하는 부분 구간이 먼저 계산되는 순서인가?
• 첫 행동과 마지막 행동 중 어느 쪽을 고정해야 구간이 독립되는가?

디버깅 기준: 길이 1과 길이 2 구간의 값을 직접 계산해 초기화와 순서를 검증한다.

행렬 곱셈과 인접 합치기는 중간 분할점 k를 고른다. Burst Balloons는 구간에서 마지막으로 터뜨릴 풍선을 고르면 양쪽 부분 문제가 독립된다.

구간 DP가 보이면 먼저 “첫 행동”보다 “마지막 행동”을 고정했을 때 부분 문제가 분리되는지도 확인한다.

구현 순서

구간 길이 1의 기저 상태를 먼저 만든다. 길이를 2부터 증가시키며 각 [l,r]에서 가능한 분할점이나 마지막 선택을 순회한다. 구간 합이 반복해서 필요하면 prefix sum으로 O(1)에 계산해 DP 전이 자체에 집중한다.

트리를 한 정점에 루팅하면 각 간선의 방향이 부모와 자식으로 정해진다. 자식을 모두 계산한 뒤 부모를 계산하므로 순환 없이 DP를 수행할 수 있다.

dp[u][0/1]에서 두 번째 축은 정점 u의 선택 여부처럼 부모 전이에 영향을 주는 경계 상태다.

스스로 설명해 보기

• 부모에게 전달할 자식 서브트리의 경계 정보는 무엇인가?
• 선택한 부모가 자식의 허용 상태를 어떻게 제한하는가?
• rerooting에서 현재 자식의 기여를 제외했는가?

디버깅 기준: 정점 하나, 일자 트리, 별 모양 트리에서 각 상태의 의미를 손으로 확인한다.

첫 DFS에서 아래쪽 기여를 계산하고, 두 번째 DFS에서 부모 방향의 기여를 자식에게 전달한다. 자식 v에게 값을 보낼 때는 v가 만든 기여를 제외해야 한다.

이를 빠르게 하려면 자식 기여의 최댓값 두 개, prefix/suffix 합처럼 “한 자식을 제외한 전체”를 계산할 구조를 준비한다.

구현 순서

부모 배열과 DFS 순서를 먼저 만든 뒤 역순으로 자식 DP를 계산한다. rerooting은 아래쪽 값을 만든 첫 순회와 위쪽 값을 전달하는 두 번째 순회로 분리한다. Tree Knapsack은 자식 하나를 합칠 때마다 임시 배열을 새로 만들고 유효한 선택 개수 범위만 순회한다.

원소 수가 작을 때 집합을 비트마스크로 표현하면 방문 집합이나 선택 집합을 배열 인덱스로 사용할 수 있다. mask | (1<<x)는 x를 추가하고, mask & (1<<x)는 포함 여부를 검사한다.

dp[mask]에 집합만으로 미래가 결정되는지, 마지막 위치까지 필요한지 구분하는 것이 첫 설계 단계다.

스스로 설명해 보기

• mask의 켜진 비트는 처리 완료인가, 아직 남은 원소인가?
• 같은 mask라도 마지막 위치가 다르면 미래 비용이 달라지는가?
• 예상 상태 수와 상태당 전이 수를 곱해 제한 안에 드는가?

디버깅 기준: N=3의 모든 mask를 출력해 빠진 전이와 중복된 순회를 찾는다.

TSP에서는 같은 방문 집합이어도 마지막 정점에 따라 다음 이동 비용이 달라져 dp[mask][last]가 필요하다. 행 프로필 DP에서는 현재 행의 배치와 이전 행의 배치가 호환되는지 검사한다.

마스크는 “전체 선택 기록”이 아니라 미래 전이에 필요한 경계 정보를 압축하는 도구다.

구현 순서

mask의 의미를 주석으로 고정하고 빈 집합의 기저값을 설정한다. 각 전이에서 새 비트를 추가하는지 제거하는지 한 방향만 사용한다. dp[mask][last]라면 last가 mask에 포함된 상태만 유효하다는 불변식도 유지한다.

dp[pos][tight][started][state]에서 pos는 현재 자리, tight는 지금까지 상한과 같은 prefix인지, started는 선행 0을 지나 실제 숫자가 시작됐는지를 나타낸다.

state에는 이전 숫자, 사용 숫자 집합, 자릿수 합이나 값의 나머지처럼 문제 조건에 필요한 정보만 넣는다.

스스로 설명해 보기

• tight가 0이 되는 정확한 순간을 설명할 수 있는가?
• 선행 0과 숫자 안의 실제 0을 started로 구분했는가?
• 문제 조건에 필요한 이전 숫자, 집합, 나머지만 state에 넣었는가?

디버깅 기준: 작은 상한까지 완전 탐색한 결과와 Digit DP의 개수를 비교한다.

게임 DP는 한 번이라도 패배 상태로 이동할 수 있으면 현재를 승리 상태로 둔다. 확률 DP는 전이 확률을 곱해 분포를 합치고, 기댓값 DP는 다음 상태의 기댓값에 한 행동의 비용을 더한다.

자기 자신으로 돌아오는 확률이 있다면 식의 양변을 정리해야 하며, 단순한 위상 순서 DP처럼 바로 대입하면 안 될 수 있다.

구현 순서

숫자를 가장 높은 자리부터 배열로 분리한다. 재귀 인자는 pos, tight, started와 문제별 state만 포함하고, 상한에 더 이상 붙어 있지 않은 상태는 메모이제이션한다. 0 자체를 세는지 여부는 마지막 pos의 반환값에서 명시적으로 처리한다.

먼저 정답이 맞는 단순 DP를 설계하고 복잡도를 상태 수 × 전이 후보 수로 분해한다. 시간 초과의 원인이 되는 반복문이 어떤 최솟값, 합, 구간 후보를 계산하는지 확인한다.

Prefix Sum, deque, Divide and Conquer, Knuth, SOS DP는 서로 교환 가능한 마법이 아니다. 각 기법이 요구하는 전이 구조와 단조성 또는 포함 관계를 증명한 뒤 적용한다.

스스로 설명해 보기

• 기본 DP의 상태 수와 후보 수를 분리해 병목을 찾았는가?
• 적용하려는 최적화의 단조성 또는 구간 비용 조건을 증명했는가?
• 최적화 전후가 같은 상태와 초기값을 사용하는가?

디버깅 기준: 느리지만 명확한 기준 풀이와 무작위 작은 입력을 대조한다.

Divide and Conquer Optimization은 최적 분할점의 단조성이 필요하다. Knuth Optimization은 더 강한 구간 비용 조건과 최적점 범위를 사용한다. SOS DP는 모든 부분집합 또는 상위집합의 값을 마스크 축별로 전파한다.

조건을 확인하지 않고 기법 이름만 보고 적용하면 빠르지만 틀린 풀이가 된다. 작은 입력의 O(N²) 또는 O(N³) 기준 풀이와 무작위 대조도 좋은 검증 방법이다.

구현 순서

정답이 검증된 기준 DP를 먼저 보존한다. 최적화 버전은 같은 상태 정의와 초기값으로 별도 구현하고 작은 무작위 입력을 수천 번 대조한다. 성능 측정에서는 전체 실행 시간이 아니라 실제 병목 전이의 호출 횟수와 자료구조 연산 수를 확인한다.