n번째 피보나치 수 구하기를 분할정복 알고리즘으로 풀면 재귀 호출의 횟수가 n에 대해 지수 $2^n$로 증가함.

→ 분할한 입력사례가 지수만큼 많기 때문…

하향식 문제풀이 방식은 분할한 입력사례들끼리 서로 관련이 없는 정렬 문제를 푸는 경우 이 방식이 잘 통함

• 하지만 n번째 피보나치 수 구하는 문제는 분할한 입력사례들이 여러 번 중복해서 나타남.
  • ex. 5째 피보나치 수를 구하기 위해서 4째와 3째 피보나치 수를 구해야함. 하지만 4째와 3째 피보나치 수를 구하기 위해서 둘 다 2째 피보나치 수가 필요함 → 이렇게 되면 2째 피보나치 수는 두 번 계산이 됨

→ 분할한 입력사례들이 서로 관련이 있거나 두 번 이상 나타나는 문제를 분할정복 알고리즘으로 풀면 같은 입력사례를 중복 계산하게 되므로 매우 비효율적임

이 장에서의 동적계획은 분할정복과 문제해결 방향이 거꾸로임

• 문제의 입력사례를 분할하여 문제를 푼다는 점은 분할정복과 비슷
• 하지만 동적계획은 분할한 입력사례를 재귀 호출하여 답을 얻는 대신, 가장 작은 입력사례의 압을 먼저 구하여 저장해놓고, 필요하면 꺼내 씀.

동적계획 알고리즘은 배열을 이용하여 상향식으로 해답을 구함 = 상향식 접근방법

동적계획 알고리즘의 개발절차

1. 문제의 입력사례에 대해서 해답을 계산하는 재귀 관계식을 세움
2. 작은 입력사례부터 먼저 해결하는 상향식 방법으로 전체 입력사례에 대한 해답을 구함

3.1 이항계수 구하기

이항계수의 식은 다음과 같음