Search

0.5.8.2 Source Code

Sedgewick gives a dynamic programming example of efficiently calculating the nth Fibonacci number as follows:

/* 
 * we will use this array to store computations and avoid repeating
 * work that has already been completed.
 *
 */
int known_fib[MAX_FIB];


/*
 * assume that known_fib is initialized to all UNKNOWN or with valid
 * Fibonnacci numbers
 *
 */
int fib(int i) {

  int t;

  if (known_fib[i] != UNKNOWN) return(know_fib[i]);
  if (i == 0) t = 0;
  if (i == 1) t = 1;
  if (i > 1) t = fib(i - 1) + fib(i - 1);
  known_fib[i] = t;
  return(t);
}