[ALGORITHMS] Dynamic Programming

1. 동적 계획법(Dynamic Programming)이란?

• 수학적 최적화 방법이자 컴퓨터 프로그래밍 기법

• 복잡한 문제를 작은 하위 문제로 나누고, 각 하위 문제를 한 번만 계산한 후 결과를 메모리에 저장하여 효율 UP

• 분할 정복(Divide and Conquer)과 유사하지만, 중복 계산을 피하기 위해 재귀(recursion)를 사용하지 않거나 최소화하는 것이 특징

2. 동적 계획법이 가능한 전제 조건

1) Overlapping Sub-problems (중복되는 하위 문제)

• 동일한 하위 문제가 여러 번 반복해서 등장함.
• 예: 피보나치 수열

2) Optimal Substructure (최적 부분 구조)

• 전체 문제의 최적 해는 하위 문제들의 최적 해로부터 만들어짐.
• 예시 비교: 이진 탐색(Binary Search)은 중복 문제 없음 vs 피보나치 수열은 중복 하위 문제가 있어 DP 적용 가능.

3. 주요 기법: Tabulation vs Memoization

Tabulation (Bottom-Up) : 반복문 사용

• 가장 작은 하위 문제부터 시작하여 큰 문제로 확장

// Bottom-Up 방식 (Tabulation)
public static long bottomUp(int n) {
    for (int i = lastFibIndex + 1; i <= n; i++)
        fib[i] = fib[i - 1] + fib[i - 2];
    if (n > lastFibIndex) lastFibIndex = n;
    return fib[n];
}

Memoization (Top-Down) : 재귀 + 캐싱

• 이미 계산된 값을 저장해서 재계산 방지

// Top-Down 방식 (Memoization)
public static long topDown(int n) {
    if (n < lastFibIndex) return fib[n];
    fib[n] = topDown(n-2) + topDown(n-1);
    lastFibIndex = n;
    return fib[n];
}

4. DP 문제 해결 단계

Step 1: DP 문제인지 확인

• 최적화 문제 (최소, 최대값 찾기)
• 카운팅 문제 (조건을 만족하는 조합의 수)
• 중복되는 하위 문제가 있는지 확인

Step 2: 상태(state) 정의

• 상태는 문제를 표현할 최소한의 파라미터로 정의
• 예: 피보나치에서는 상태 = n

Step 3: 상태 간 관계식 수립

• 상태 전이(transitions)를 수식으로 표현
• 예: Fib(n) = Fib(n-1) + Fib(n-2)

Step 4: 구현 (Top-Down 또는 Bottom-Up)

• 배열이나 캐시 구조 사용
• 반복문 혹은 재귀로 구현

---

대표 예시 문제 1 : Coin Change - Count Ways to Make Sum

Given an integer array of coins[] of size n representing different types of denominations and an integer sum, the task is to count all combinations of coins to make a given value sum.

Note: Assume that you have an infinite supply of each type of coin.

Examples 1)
Input: sum = 4, coins[] = [1, 2, 3]
Output: 4
Explanation: There are four solutions: [1, 1, 1, 1], [1, 1, 2], [2, 2] and [1, 3]

Examples 2)
Input: sum = 10, coins[] = [2, 5, 3, 6]
Output: 5
Explanation: There are five solutions:
[2, 2, 2, 2, 2], [2, 2, 3, 3], [2, 2, 6], [2, 3, 5] and [5, 5]

Solution

점화식 : dp[i] += dp[i - coin]

class Itm {

    static int count(int[] coins, int sum) {
        int n = coins.length;
        int[] dp = new int[sum + 1];

        dp[0] = 1;

        for (int coin : c) {
            for (int amount = coin; amount <= n; amount++) {
                dp[amount] += dp[amount - coin];
            }
        }
                
        return dp[sum];
    }

    public static void main(String[] args) {
        int[] coins = {1, 2, 3};
        int sum = 5;
        System.out.println(count(coins, sum));
    }
}

---

대표문제 2) Knapsack Problem

기본 문제 (0/1 Knapsack):

• "무게 제한이 있는 배낭에, 물건을 담되, 가치(value) 를 최대화하라"
• 각 물건은 무게(weight)와 가치(value) 를 가짐
• 한 번씩만 선택 가능 (0/1 조건)
• 배낭은 최대 무게 W까지 가능
• 물건들을 선택해서 가치의 합을 최대로

Example

물건 3개: weights = [1, 3, 4], values = [15, 20, 30]
배낭 최대 무게: W = 4

Solution

dp[i][w] = i번째까지의 물건으로, 무게 w를 넘지 않게 담았을 때의 최대 가치

if (weight[i-1] <= w)
    dp[i][w] = max(dp[i-1][w],  // 안 담음
                  value[i-1] + dp[i-1][w - weight[i-1]])  // 담음
else
    dp[i][w] = dp[i-1][w]; // 담을 수 없음