동적계획 알고리즘이란? 동적계획은 분할한 입력사례를 재귀 호출해 답을 얻고, 그 보다 작은 입력사례의 답을 먼저 구해 저장해놓고, 필요하면 꺼내 쓰는 알고리즘이다. 분할정복과는 달리 상향식(bottom-up) 접근 방법이다. 동적계획 알고리즘의 개발단계는 다음과 같다. 1. 문제의 입력사례에 대해서 해답을 계산하는 재귀 관계식을 세운다. 2. 작은 입력사례부터 먼저 해결하는 상향식 방법으로 전체 입력사례에 대한 해답을 구한다. 이항계수 구하기 이항계수 (binomial coefficient)는 다음과 같다. $$\left(\begin{array}{c}n\\ k\end{array}\right) = \frac{n!}{k!(n-k)!} \;\; \mathrm{for} \;\;0 \leq k \leq n$$ 위..