Fibonacci Sequence Dynamic Programming

Problem: Write the code for nth Fibonacci number.

Solution: There are basically two approaches to solving the Fibonacci problem. Lets looks at the definition of Fibonacci series first.

The Fibonacci series is defined as follows

F(n) = 0 for n = 0
       1 for n = 1
       F(n-1) + F(n-2) for n > 1

If we translate that to the C language we get:

int RecursiveFibonacci(int n)
{
    if(n == 0) return 0;
    if(n == 1) return 1;
    return RecursiveFibonacci(n-1) + RecursiveFibonacci(n-2);
}

Now, whats the running time of the above program. It's horrible!! It's exponential. Why? We have a lot of duplicate work being done on each recursive call.

Typically when you are doing duplicate work, Dynamic Programming can come to rescue. Now, I don't want to go into too much detail on dynamic programming, but you have 2 approaches to Dynamic Programming. One is the bottom up approach and the second is called the top down approach. Calculating F(n) given F(n-1) would be a bottom up approach and calculating F(n) by recursively calling F(n-1) and F(n-2) would be top down. For a thorough treatment of dynamic programming see a Algorithms text or this wikipedia entry.

We can improve the above RecursiveFibonacci function by caching results of previous calculations. Doing this greatly reduces the number of recursive calls and improves the program efficiency. This is an example of top down dynamic programming.

int RecursiveFibonacci(int n)
{
    if(n == 0) return 0;
    if(n == 1) return 1;
   
    if(cache[n] == null)
      cache[n] = RecursiveFibonacci(n-1) + RecursiveFibonacci(n-2);
    return cache[n];
}

Now lets look at the bottom up dynamic programming approach. For a given n we would need to have F(n-1), F(n-2), F(n-3) ... F(0) already solved. In this case we'll start at the bottom and work our way up.

int GetFibonacci(int n)
{
    if(n == 0) return 0;
    if(n == 1) return 1;
   
    last1 = 0;
    last2 = 1;   
    ans = 0;

    for(int i=0; i < n-1; i++)
    {
       ans = last1 + last2;
       last1 = last2;
       last2 = ans; 
    }

    return ans;
}

We could have used a cache like we used in the top down approach, but all we really need is the last 2 results. We can get away with just using 2 variables. This is also an iterative solution which is better compared to the recursive one because of the absence of the stack overhead involved in recursive calls.