6-1강 - Dynamic Programming 1 (DP, Binomial Coefficient)

0. Dynamic Programming

(instance I [size는 n]이 있을 때,)

1) bottom-up 방식 - recursive property

1> bottom-up으로 cost 계산

instance I에 대한 optimal solution은 I의 sub-instance에 대한 optimal solution을 이용하여 푼다.

2> top-down으로 sol 구한다.

sub-instance에 대한 cost를 모두 구해놓고 (bottom-up)

이들을 고려하여 다시 top-down으로 optimal solution을 구한다.

2) Programming = array(table)

1> Divide & Conquer와 다른 점

sub-instance들이 중복되며 solution을 구한다.

2> 그래서 solution을 구한 sub-instance를 array에 기록해둡니다.

- sub-instance에 대한 optimal solution cost

- solution을 구하기 위한 흔적을 남겨둔다.

(그래서 한 번 본 sub-instance가 나타나면 기록한 array에서 꺼내 사용합니다.

 

1. The Binomial Coefficient

1) The Binomial Coefficient

1> 정의

2> recursion form

cf> 분할 정복을 적용하면?

divde 했음에도 size가 커지므로(중복) exponential complexity를 가진다.

그러므로 Dynamic programming을 적용해본다.

 

2) Dynamic programming 

1> recursive from

-> memo할 table을 만든다.

2> memo를 이용한 bottom-up 방식 적용