동적계획법(Dynamic programming)-1

동적계획법

(DP)

Fibonacci Numbers

->recursion으로 하니 많은 계산이 중복됨

Memoization

: 중간 계산 결과를 cahing함으로써 중복 계산을 피함

bottom-up 방식

배열을 이용해 순환식을 bottom-up방식으로 계산하는 것은 동적계획법이라ㅗㄱ 한다.

이항계수(Binomial Coefficient)

->많은 계산이 중복됨

Memoization

Dynamic Programming

Memoization vs Dynamic Programming

- 순환식의 값을 계산하는 기법들이다.

- 둘 다 동적계획법의 일종으로 보기도 한다.

- Memoization 은 top-down방식이며, 실제로 필요한 subproblem만을 푼다.

- 동적계획법은 bottom-up 방식이며, recursion에 수반되는 overhead가 없다.