메모이제이션을 통한 동적 프로그래밍

동적 프로그래밍(dynamic programming)은 하위 문제가 중첩되는 재귀 문제를 최적화하는 절차다.

 

메모이제이션(memoization)은 하위 문제가 중첩될 때 재귀 호출을 감소시키는 간단하면서도 아주 뛰어난 기법이다.

본질적으로 메모이제이션은 먼저 계산한 함수 결과를 기억해 재귀 호출을 감소시킨다.

 

* 메모이제이션 구현

int fib(int n, int[] memo) {

    if (n == 0 || n == 1) return n;
    
    // memo 테이블을 확인해 fib(n)이 이미 계산된 건지 본다.
    if (memo[n] == 0) { // 값이 없으면 재귀호출 실행
        memo[n] = fib(n-2, memo) + fib(n-1, memo);
    }
    
    return memo[n]; // 이미 계산된 값이 있으면 그 값을 리턴.
}

 

* DP(Dynamic Programming) 문제 푸는 공식 3단계

1) DP 테이블 정의

2) 점화식 찾기

3) 초기값 정하기