Finding the fibonacci numbers (eficient way)

Finding the fibonacci numbers (Dynamic Programming)

This recursive program to find Fibonacci numbers is very common :

int fib(int n)
{
   if ( n <= 1 )
      return n;
   return fib(n-1) + fib(n-2);
}

Here is the recursion tree for this program

                         fib(5)

                     /             \

               fib(4)                fib(3)

             /      \                /     \

         fib(3)      fib(2)         fib(2)    fib(1)

        /     \        /    \       /    \

  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)

  /    \

fib(1) fib(0)

It is clear that if  we use this implementation we have to compute several values  repeatedly. For eg in the above tree f(3) is computed twice, f(2) thrice. So, instead of computing it again if we can reuse the old value, our program would be more efficient.
Here is the dynamic programming approach to solve the problem: 

1) Bottom Up: This program builds a table in bottom up fashion and returns the last entry from the table.

#include<stdio.h>
int fib(int n)
{
  int f[n+1];
  int i;
  f[0] = 0;   f[1] = 1; 
  for (i = 2; i <= n; i++)
      f[i] = f[i-1] + f[i-2];
 
  return f[n];
}
  
int main ()
{
  int n = 9;
  printf("Fibonacci number is %d ", fib(n));
  return 0;
}

2) Top Down : This is similar to recursive approach, but in this program we use a look up table which is initialised to a sentinel value. Whenever we need a solution to a sub problem we check into the look up table if it is already computed we use it directly otherwise it is computed and stored in the look up table so that it can be used later.

#include<stdio.h>
#define MAX_SIZE 100
 
int lookup[MAX_SIZE];
 
int fib(int n)
{
   if (lookup[n] == -1)
   {
      if (n <= 1)
         lookup[n] = n;
      else
         lookup[n] = fib(n-1) + fib(n-2);
   }
 
   return lookup[n];
}
 
int main ()
{
  int i,n = 10;
   for (i = 0; i < MAX_SIZE; i++)
    lookup[i] = -1;
 
printf("Fibonacci number is : %d ", fib(n));
  return 0;
}