DP(Dynamic Programming)

란?

복잡한 문제를 작은 하위 문제로 나누어 푸는 알괴즘 설계 기법 임. 주로 중복되는 하위 문제(Subproblems) 가 있고, 이들을 한 번만 계산하고 그 값을 재사용 할 수 있을 때 매우 효율적으로 작동함.

---

1. DP 의 핵심 개념

중복되는 부분 문제(Overlapping Subproblems)

• 큰 문제를 해결하기 위해 같은 작은 문제를 여러 번 반복해서 푸는 경우

• 예시 : 피보나치 수열 - f(n) = f(n-1) + f(n-2) 이고, f(n-1) 과 f(n-2) 를 구할 때 또 그 하위 문제들이 반복적으로 호출됨.

최적 부분 구조 (Optimal Substructure)

• 문제의 최적 해가 그 하위 문제들의 최적 해를 이용해 구할 수 있을 때

• 즉, 하위 문제들의 답을 합쳐서 전체 문제의 답을 구할 수 있음.

---

2. DP 의 해결 방법

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

• 큰 문제를 풀기 위해 재귀적으로 작은 문제들을 풀어감.

• 이미 푼 문제는 메모리(배열, 딕셔너리 등) 에 저장해서 다시 계산하지 않음

• Java 예시:

Map<Integer, Integer> memo = new HashMap<>();

int fib(int n) {
    if(n <= 1) return n;
    if(memo.containsKey(n)) return memo.get(n);
    int result = fib(n-1) + fib(n-2);
    memo.put(n, result);
    return result;
}

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

• 작은 문제부터 차례대로 풀어서 답을 구함.

• 별도의 재귀 호출이 없고, 반복문으로 구현됨.

• Java 예시:

int fib(int n) {
    if(n <= 1) return n;
    int[] db = 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];
    }
    
    return dp[n];
}

---

3. 자주 나오는 DP 문제 유형

문제 유형	예시	키 포인트
1차원 DP	피보나치, 계단 오르기	dp[i] = dp[i-1] + dp[i-2]
2차원 DP	LCS(Longest Common Subsequence), LCS	dp[i][j] 를 의미적으로 정의
배낭 문제	0/1 Knapsack	dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight]+value)
구간 DP	팰린드롬 분할, 행렬 곱 최적화	구간 dp[l][r] 에 대한 점화식
상태 압축 DP	여행자 문제, 외판원 순회	비트 마스크 활용
DP + DFS	게임판 탐색, 경로 탐색	DFS 내에서 dp[x][y] 저장
DP + 슬라이딩 윈도우	최대 부분합	메모리 최적화

---

4. DP 문제 풀이 순서

1. 문제를 보고 중복되는 계산이 있는지 파악

2. 문제를 작은 하위 문제들로 나눌 수 있는지 판단.

3. dp 배열(혹은 메모 테이블)의 정의와 의미 부여

4. 점화식(이전 상태에서 현재 상태로 가는 방법) 도출

5. 초기값 설정

6. 반복문 or 재귀로 구현

7. 메모리나 시간 최적화 필요시 슬라이딩 윈도우, 상태 압축 등 적용

---

5. 예제 : 계단 오르기(한 번에 1칸 또는 2칸 오를 수 있음)

• 목표 : n 칸 계단을 오르는 방법의 수

• 점화식 : dp[i] = dp[i - 1] + dp[i - 2]

• 초기값 : dp[0] = 1 , dp[1] = 1

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