static long Fibonacci(int n)
{
    if (n < 0) throw new ArgumentOutOfRangeException(nameof(n));
    if (n <= 1) return n;

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

구조

동적 프로그래밍은 같은 계산을 여러 번 반복하지 않도록 답을 저장합니다. 피보나치 재귀는 같은 Fib(k)를 계속 다시 계산하지만, DP는 한 번 계산한 값을 재사용합니다.

Fib(5)
-> Fib(4) + Fib(3)
-> Fib(3)이 여러 번 등장

DP가 잘 맞는 문제는 보통 두 조건을 가집니다.

메모이제이션과 타뷸레이션

메모이제이션은 재귀를 유지하면서 계산 결과를 캐시에 저장합니다. 타뷸레이션은 작은 상태부터 반복문으로 테이블을 채웁니다. 모든 상태를 계산하지 않아도 되는 경우는 메모이제이션, 재귀 깊이가 부담되거나 계산 순서가 명확한 경우는 타뷸레이션이 읽기 쉽습니다.

static long FibonacciMemoized(int n)
{
    if (n < 0) throw new ArgumentOutOfRangeException(nameof(n));

    var memo = new long?[n + 1];

    long Solve(int index)
    {
        if (index <= 1) return index;
        if (memo[index] is long cached) return cached;

        long value = checked(Solve(index - 1) + Solve(index - 2));
        memo[index] = value;
        return value;
    }

    return Solve(n);
}

이 예제에서 null은 아직 계산하지 않은 상태이고 0은 실제 피보나치 답입니다. 정답이 음수가 될 수 있거나 -1도 유효한 문제에서는 -1을 미계산 표식으로 쓰면 안 됩니다. 도달 불가능 상태는 충분히 큰 값, 별도 방문 배열, nullable 값 중 문제의 답 범위와 겹치지 않는 방법으로 표현합니다.

하향식(top-down)은 실제로 필요한 상태만 계산할 수 있지만 재귀 깊이만큼 call stack을 씁니다. 상향식(bottom-up)은 순서를 직접 정하므로 깊은 재귀를 피하기 좋습니다. 피보나치처럼 직전 두 값만 필요하면 배열도 두 변수로 압축할 수 있지만, 이전 선택을 복원해야 하는 문제에서는 predecessor나 choice 정보를 따로 남겨야 합니다.

상태 잡기

DP는 코드보다 상태 정의가 더 중요합니다. dp[i]가 “i번째를 반드시 포함한 답”인지, “i번째까지 고려한 답”인지가 다르면 전이식도 달라집니다.

0/1 배낭처럼 같은 항목을 한 번만 고르는 DP를 1차원 배열로 압축할 때는 용량을 큰 쪽에서 작은 쪽으로 갱신합니다. 작은 쪽부터 갱신하면 같은 항목을 이번 반복 안에서 다시 참조해 무제한 선택 문제로 바뀝니다. 반대로 무제한 선택 문제는 작은 쪽에서 큰 쪽으로 갱신합니다.

주의할 점