동적계획법

다음 상태를 저장하고, 사용하기 (메모이제이션)

 

쉬운 난이도부터 어려운 난이도까지… (피보나치, Knapsack…)

 

푸는 순서

1. 상태를 정의한다.

2. 점화식을 찾는다.(구한다)

3. 시간복잡도를 계산한다.

4. 코딩한다.

 

푸는 방법

1. Top-Down (재귀) - C나 Java에서 더 빠른 경우가 많음

2. Botton-Up (반복문) - 점화식대로 쓰면 돼서 더 편함