DP 핵심개념 4가지

🧠 DP란?

• *동적 계획법(Dynamic Programming)**은
• *“복잡한 문제를 하위 문제로 나누고, 그 결과를 저장해서 중복 계산을 피하는 알고리즘 기법”**

언제 쓰는가?

• 문제를 여러 부분 문제(subproblem)로 나눌 수 있을 때
• 같은 문제가 반복해서 나타날 때
• 예: 피보나치 수, 최소 비용 계산, 최장 증가 부분 수열 등

---

✅ DP의 4가지 기본 구성요소

항목	설명	예시
① 기저 조건 (Base Case)	재귀나 반복이 종료되는 조건	if (i >= n) return 0;
② 점화식 (Recurrence Relation)	큰 문제를 작은 문제로 쪼갤 수 있는 규칙	dp[i] = cost[i] + min(dp[i+1], dp[i+2])
③ 메모이제이션 (Memoization)	이미 구한 결과를 기억해두기	map.put(i, result)
④ 기본 구조	재귀(Top-down) 또는 반복문(Bottom-up)	result(i), for문

---

① 기저 조건 (Base Case)

• 말 그대로 “이제 더 이상 쪼갤 수 없는 최소 단위”
• 보통 재귀 함수에서 종료 조건

if (i >= cost.length) return 0;

→ 계단을 다 오르면 추가 비용은 0이니까 여기서 멈추는 것

---

② 점화식 (Recurrence Relation)

• 문제를 작게 나눴을 때의 규칙
• 예: 지금 위치에서 1칸, 2칸 갈 수 있다면

dp[i] = cost[i] + min(dp[i+1], dp[i+2]);

→ 지금 위치의 비용 + 다음 계단 중 더 적은 비용

---

③ 메모이제이션 (Memoization)

• 중복 계산을 방지하는 기법
• 자바에선 주로 Map<Integer, Integer> 사용해서 기억해둠

if (memo.containsKey(i)) return memo.get(i);

→ 이미 계산한 위치는 다시 계산 안 함

---

④ 기본 구조

🎯 Top-down 구조 (재귀 + 메모이제이션)

int dp(int i) {
    if (i >= cost.length) return 0;
    if (memo.containsKey(i)) return memo.get(i);

    int result = cost[i] + Math.min(dp(i+1), dp(i+2));
    memo.put(i, result);
    return result;
}

🎯 Bottom-up 구조 (반복문 + 배열)

int[] dp = new int[n];
dp[0] = cost[0];
dp[1] = cost[1];
for (int i = 2; i < n; i++) {
    dp[i] = cost[i] + Math.min(dp[i-1], dp[i-2]);
}
return Math.min(dp[n-1], dp[n-2]);

---

정리해보면

[DP 알고리즘 구조]
1. 기저 조건 → 언제 멈출지?
2. 점화식 → 앞/뒤 값으로 계산하는 규칙
3. 메모이제이션 → 계산한 값 저장
4. 구조 → top-down(재귀) or bottom-up(반복문)

---

예시 문제: 피보나치 수

| 문제 | n번째 피보나치 수를 구하라 (1, 1, 2, 3, 5, 8, …) |

| 점화식 | dp[n] = dp[n-1] + dp[n-2] |

| 기저조건 | dp[1] = 1, dp[2] = 1 |

| 메모이제이션 | Map 또는 int[] dp |

| 구조 | top-down: 재귀 + memo / bottom-up: 반복문 |