Dynamic Programming - Top Down, Bottom Up

다이나믹 프로그래밍은 메모이제이션을 사용해 이전에 사용한 값을 그대로 읽어 사용함으로서 극적으로 줄일 수 있다. 여기서 메모이제이션의 개념을 보면 마치 캐시 와 비슷해보인다. 그래서 혹자는 캐시질이라고도 한다.

 

Top - Down

큰 숫자에서 작은 숫자까지 내려가면서 솔루션을 구하는 방법이다. 

 

rec(N){

 dp[N] = min(rec(N - 1), rec(N - 2))

}

Bottom - Up

작은 숫자부터 시작하며 다음 숫자에서 이전의 값을 사용하는 정석적인 dp 방식이다. 주로 점화식을 찾아서 적용시킬 때 사용된다.

for(int i = 2; i <= 10; i++){
	dp[i] = dp[i - 1] + dp[i - 2]; 
}