동적 계획법

복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법

1. 큰 문제를 작은 문제로 나눌 수 있어야 함.
2. 작은 문제들이 반복돼 나타나고 사용되며 작은 문제들의 결과값은 항상 같아야 함.
3. 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 DP 테이블을 이용.
4. 동적 계획법은 톱-다운 방식과 바텀-업 방식으로 구현할 수 있음.

동적 계획법의 예시

피보나치 수열 공식

D[0] = 0, D[1] = 1;
D[n] = D[n - 1] + D[n - 2];