동블

그래프 뷰

06. DP

5 min read

DP

Summary

DP는 점화식을 외우는 게 아니라 dp 상태 정의를 먼저 세우는 유형이다.
초기값과 정답 위치를 틀리면 점화식이 맞아도 틀린다.

사고 과정

1. 경우의 수 / 최댓값 / 최솟값 / 가능 여부 중 무엇인가?
2. dp[i]가 정확히 무엇을 의미하는가?
3. 마지막 선택은 무엇인가?
4. 그 선택 직전 상태는 어디인가?
5. 초기값은 작은 n을 직접 세었는가?
6. 정답은 dp[N]인가, 전체 dp 중 max/min인가?

0/1 배낭 검증 템플릿

Info

0/1 배낭은 같은 물건을 한 번만 써야 하므로 무게를 뒤에서 앞으로 돈다.

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int capacity = Integer.parseInt(st.nextToken());
 
        int[] dp = new int[capacity + 1];
 
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int weight = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
 
            for (int w = capacity; w >= weight; w--) {
                dp[w] = Math.max(dp[w], dp[w - weight] + value);
            }
        }
 
        System.out.println(dp[capacity]);
    }
}

LIS 검증 템플릿

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
 
        int[] lis = new int[n];
        int len = 0;
 
        for (int x : arr) {
            int pos = lowerBound(lis, len, x);
            lis[pos] = x;
            if (pos == len) len++;
        }
 
        System.out.println(len);
    }
 
    static int lowerBound(int[] arr, int len, int target) {
        int left = 0;
        int right = len;
 
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < target) left = mid + 1;
            else right = mid;
        }
 
        return left;
    }
}

LCS 검증 템플릿

import java.io.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String a = br.readLine();
        String b = br.readLine();
 
        int[][] dp = new int[a.length() + 1][b.length() + 1];
 
        for (int i = 1; i <= a.length(); i++) {
            for (int j = 1; j <= b.length(); j++) {
                if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
 
        System.out.println(dp[a.length()][b.length()]);
    }
}

자주 나오는 DP 유형

유형상태 예시
피보나치/타일링dp[i] = 길이 i를 만드는 경우
계단/스티커dp[i][state] = i번째에서 state로 끝나는 최댓값
경로 DPdp[i][j] = (i,j)까지의 최댓값/경우의 수
0/1 배낭dp[w] = 무게 w에서 얻는 최대 가치
LISlis[len] = 길이 len+1 증가수열의 최소 끝값
LCSdp[i][j] = a[0..i), b[0..j) LCS 길이
구간 DPdp[l][r] = l~r 구간의 답
비트마스크 DPdp[mask][last] = 선택 집합과 마지막 상태

점화식 체크 문장

dp[i]는 ________ 를 의미한다.
dp[i]는 ________ 경우에서 온다.
초기값은 ________ 이다.
정답은 ________ 에 있다.

주의점

실수주의
dp 의미 불명확한 문장으로 먼저 정의
초기값 누락작은 n 직접 계산
음수 인덱스i-2, i-3 접근 전 범위 확인
정답 위치 착각항상 dp[N]이 답은 아님
경우의 수 overflowmod 또는 long 확인
재귀 깊이Java는 Bottom-Up이 안전한 경우 많음

백지 복원

1. 0/1 배낭은 왜 w를 뒤에서 앞으로 도는가?
2. LIS O(N log N)에서 lowerBound를 쓰는 이유는?
3. LCS에서 문자가 같을 때 점화식은?
4. DP 문제를 만나면 가장 먼저 채울 문장은?

관련 문서