DP 정리

다이나믹 프로그래밍 (DP)

🔍 개요

• 큰 문제를 작은 문제로 나누어, 작은 문제의 해를 저장하고 재활용하여 큰 문제를 해결
• 조건
  1. 중복되는 부분 문제 → 같은 계산이 반복됨 (ex. 피보나치 수열)
  2. 최적 부분 구조 → 큰 문제의 최적해가 작은 문제의 최적해들로부터 구성 가능

---

🤔 핵심 접근 방법

(1) Top-Down (재귀 + 메모이제이션)

• 큰 문제 → 작은 문제로 분할
• 재귀 함수 안에서 dp[] 값이 이미 계산되었는지 확인 후 재사용

static int[] dp = new int[100];
 
static int fibo(int n) {
	if(n <= 1) {
		return n;
	}
	
	if(dp[n] != 0) {
		return dp[n];  // 이미 계산됨
	}
	
	return dp[n] = (fibo(n-1) + fibo(n-2));
}

(2) Bottom-Up (반복문 + 테이블)

• 작은 문제 → 큰 문제로 확장
• 반복문으로 dp[] 배열을 채워감

int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
 
for(int i = 2; i <= n; i++) {
	dp[i] = dp[i-1] + dp[i-2];
}

---

❓ 대표 DP 유형

(A) 1차원 DP

• 피보나치 수열, 계단 오르기, 1로 만들기

// 계단 오르기: n번째 계단 오르는 방법 수
dp[i] = dp[i-1] + dp[i-2];

(B) 2차원 DP (격자 문제)

• 최소 비용 경로, 최단 경로

// (i, j)까지 최소 비용
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + cost[i][j];

(C) 배낭 문제 (Knapsack)

• 0/1 배낭: 물건을 넣거나 안 넣거나

for(int i = 1; i <= n; i++) {
	for(int w = W; w >= weight[i]; w--) {
		dp[w] = Math.max(dp[w], dp[w-weight[i]] + value[i]);
	}
}

(D) 구간 DP

• 팰린드롬 여부, 행렬 곱 최적화

(E) 문자열 DP

• LCS(최장 공통 부분 수열)

if(s1[i-1] == s2[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]);
}