동적 계획법(Dynamic Programming)

이미 계산된 결과(하위 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 설계함으로써 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다.

DP가 성립하는 조건

1. 최적 부분 구조(Optimal Substructure)
   상위 문제를 하위 문제로 나눌 수 있으며 하위 문제의 답을 모아서 상위 문제를 해결할 수 있다.
2. 중복되는 부분 문제(Overlapping Subproblem)
   동일한 작은 문제를 반복적으로 해결해야 한다.

int memo[100];
public int fibonacci(int n) {
    if (n <= 1)
        return n;
    else if (n == 2)
        return 1;
    else {
        if (memo[n] > 0)
            return memo[n];
        memo[n] = fibonacci(n-1) + fibonacci(n-2);
        return memo[n];
    }
}

DP 구현 방법

1. Top-down
   상위 문제를 해결하기 위해서 하위 문제를 재귀적으로 호출하여 하위 문제를 해결함으로써 상위 문제를 해결하는 방식이다.
   이 때 해결해놓은 하위 문제를 저장해 놓기 위해 Memoization이 사용된다.

2. Bottom-Up
   문제를 크기가 작은 문제부터 차례대로 해결
   문제 결과 값 DP 테이블에 저장해나감
   작은 문제를 풀면서 큰 문제의 답을 구한다.