Fibonacci series and dynamic programming

Tags: , ,

Find nth Fibonacci number

Given a Fibonacci series: 1, 1, 2, 3, 5, 8, 13 … which is defined as fib(n) = fib(n-1) + fib(n-2), find Nth number in this series. For example, 5th Fibonacci number is 5. 11th Fibonacci number is 89.

By definition of the Fibonacci series, it is clear that every number in the series is a sum of the last two numbers in the series. So to find nth number we just need to know (n-1)th and (n-2)th number, once we find these two numbers just adding them will give us the answer.

fib(n) = fib(n-1) + fib(n-2)

But how do we find these numbers? We keep taking the same approach for (n-1)th and (n-2)th number, i.e.
fib(n-1) = fib(n-2) + fib(n-3) and
fib(n-2) = fib(n-3) + fib(n-4)

We stop only when we hit fib(1) = 1 and fib(2) = 1.
This shows this problem has optimal substructure (i.e. an optimal solution can be constructed from optimal solutions of subproblems).

Recursive approach

The explanation/formula given above maps to simple recursion:

long long int findNthFib(int n)
{
    if(n == 1 || n == 2) return 1;
    return findNthFib(n-1) + findNthFib(n-2);
}
 
int main(void) 
{
    int N = 11;
    long long int NthFib = findNthFib(N);
    printf("%lld", NthFib);
    return 0;
}

The recursive code looks extremely simple. This is one of the advantages of recursion, it saves the efforts of writing lots of code.
Everything looks fine and we are happy with our solution until we try to find 40th or so Fibonacci number using this approach. This implementation takes over 3 secs to find 43rd Fibonacci number and the execution time increases exponentially with increasing inputs.
To find the reason behind such high runtime let’s have a look at the recursive function call tree:
dynamic programming fibonacci

In this example of finding 6th Fibonacci number, subproblems such as fib(4) and fib(3) are calculated repeatedly. Imagine how many such repeated calculations would be there when we use this implementation for finding 43rd Fibonacci number!! Hence the time 3secs.

Our recursive algorithm for this problem solves the same subproblem over and over rather than always generating new subproblems. These are called overlapping subproblems. As the two properties required for using Dynamic Programming: optimal substructure and overlapping subproblems hold, we can use DP for this problem. But before jumping to a dynamic programming solution, there’s another way to resolve the issue of overlapping subproblems in a recursive approach: Memoised approach. Let’s have a look at it first.

Memoised approach for Fibonacci series

To avoid repeated calculation in the recursive approach, we can store the base cases and the results of each fib() call in an array. The code would look like this:

long long int findNthFib(int n, vector<long long int> &memo)
{
    if (memo[n] != 0)
         return memo[n];
    memo[n] = findNthFib(n-1, memo) + findNthFib(n-2, memo);
    return memo[n];
}
 
int main(void) 
{
    int N = 43;
    vector<long long int> memo(N+1, 0);
    memo[1] = 1; memo[2] = 1;
    long long int NthFib = findNthFib(N, memo);
    printf("%lld", NthFib);
    return 0;
}

With the memoized approach the function call tree looks like this:
Fibonacci memoization

By memoizing intermediate results, we avoid repeated calculations. The time complexity of the memoized approach is O(n) and Space complexity is O(n). In both the approaches described above, observe that we took a top-down approach, i.e. we started from n and went down till 1.
Unlike recursion, Dynamic Programming uses a bottom-up approach, let’s see how it’s done in DP.

Dynamic Programming approach

In DP we start calculating from the bottom and move up towards the final solution. For this problem we first find 1st Fibonacci number, then 2nd, then 3rd and so on until Nth Fibonacci number. To aid this approach we use an array/vector where we will store the intermediate results while we move towards the final solution. The code looks like this:

int main(void) 
{
    int N = 43;
    vector<long long int> DPVec(N+1, 0);
    DPVec[1] = 1; DPVec[2] = 1;
    for (int i=3; i<=N; ++i)
    {
          DPVec[i] = DPVec[i-1] + DPVec[i-2];
    }
    printf("%lld", DPVec[N]);
    return 0;
}

Time complexity: O(n) Space complexity: O(n)
The space complexity of the DP code can be reduced by storing just the last two results instead of every result and in this way array/vector is no more required.
Moreover, there are other solutions for finding Nth Fibonacci number in O(log N) time using matrices and in O(1) constant time using the golden ratio, but this article is limited to DP approach.

This article is contributed by Bhushan Aggrawal.