| 동적프로그래밍 개념 | 동적프로그래밍 사례 | 분할정복과 동적프로그래밍 비교 |

동적 프로그래밍 사례

---------------------------------------------

unsigned  int  fib( unsigned  int  n )

{       if( n <= 1 )

             return  1;

         else

             return( fib( n-1 ) + fib( n-2 ) );

}

---------------------------------------------

비능률적인 피보나치수 계산 알고리즘

위 피보나치 함수의 수행시간은 O(2^N)이다.

T(N) >= T(N-1) + T(N-2)이므로 수행시간이 지수적으로 증가함

(예) N=5일때