DP 유형

접근법

• Q1: 최적/최대/최소/카운트 문제인가?

  • 의사결정 트리 그리기 (재귀 모델링)

• Q2: 중복 계산이 생기나?

  • 메모이제이션, 타뷸레이션

• Q3: 하위 문제(상태) 정의가 가능한가?

  • 필요한 변수파악
  • 상태 하나가 작은 문제를 완전히 대표하도록 정의
    • dp[i]가 무엇인지 정의해보기
    • dp[i][j]... dp[i][j][k]...
  • 점화식(Transition) 도출
    • 의사결정 트리의 간선을 수식으로 옮기기
      • 택하거나, 택하지 않거나
      • 이동하거나, 멈추거나
      • 선택할 때
        • min/max (dp[이전 상태] + 선택한 값, dp[지금 상태])
    • 여러 선택지 중 최대/최소/최적 값 취하기

• Q4: 문제 구조는?

  • 시간순서 or 인덱스 순 → 선형 DP
  • 이차원 격자 → 2D DP
  • 구간 분할/조합 → 구간 DP
  • 여러 상태 조건 → 상태 DP
    • 제약조건 (용량 등) → 배낭 DP
    • 트리/그래프 구조 → 트리 DP, 비트마스크 DP
  • 선형, 2D, 구간, 트리, 상태, 그리디, 케이스-분할(분기형)

• 최적 부분 구조, 중복 부분 문제 파악

• 상태 정의

• 점화식 도출

  • 최종 목표 설정
  • 경우의 수

• 초기 상태 설정

선형 DP (1D)

• 순서대로 누적 / 선택
• 피보나치, 최대 연속합, 계단 오르기

2D DP

• 2차원에서 상태 추적
• LCS, 최장 공통 부분 수열, 격자 경로

구간 DP (Interval DP)

• $[i,j]$ 범위에 최적 해 존재
• 사칙연산 괄호, 행렬 곱, 문자열 나누기
• DP 테이블의 상삼각 영역만 주로 사용 (i ⇐ j)

•   for (int len = 2; len <= n; ++len) {
    	for (int i = 0; i <= n - len; ++i) {
    		int j = i + len - 1;
    		for (int k = i; k < j; ++k) {
    			dp[i][j] = min/max(dp[i][j], dp[i][k] + dp[k+1][j] + cost);
    
    		}
    	}
    }

케이스-분할 (분기형) DP (Case-Split DP)

• 점화식이 여러개인 경우

배낭 DP (Knapsack)

• 용량/무게/자원 제한 안에서 최적 선택
• 0/1 배낭, 부분합, 동전 문제

트리 DP (Tree DP)

• 트리에서 하위 노드 결과 누적
• 루트 포함 최대합, subtree 문제

DP + 상태 전이 (with state)

• 단순 인덱스가 아닌 추가 상태 포함
• 점프와 방향, 연속성 제한, FSM, 조합

비트마스크 DP (Bitmask DP)

• 방문 여부 등 상태를 비트로 표현
• 외판원 문제(TSP), 경로 수

DP + 그리디 조건

• 일부 상태가 단조적일 때 최적화
• LIS (이분 탐색 + DP), 회의실 문제