Fibonacci Sequence Using Dynamic Programming

Fibonacci Sequence.md

Fibonacci Sequence Using Dynamic Programming

In mathematics, the Fibonacci numbers, commonly denoted F_n form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F₀ = 0 , F₁ = 1 and

F_n = F_n-1 + F_n-2 ∀ n > 1.

One has F₂ = 1. In some books, and particularly in old ones, F₀, the "0" is omitted, and the Fibonacci sequence starts with F₁ = F₂ = 1. The beginning of the sequence is thus:

(0,),1,1,2,3,5,8,13,21,34,55 ...

Simple Algorithm using Recursion

Fib(n)
    if n is less than or equals to 1
        return 1
    else
        return n = Fib(n-1) + Fib(n-2)

// C++ Code
int Fib(int n){
    if(n <= 1){
        return 1;
    }
    return Fib(n-1) + Fib(n-2)
}

Let's run the above C++ code with n = 40

It took 0.964 seconds to calculate the 40^th Fibonacci number.The above simple algorithm using recurions looks pretty good, neat and clean but extremely inefficient because of computing the same subsubproblems again and again. Let's have a look on it visually

For Example

F₇ = 13

You can see that the algorithm is working inefficiently by repeating the same calls again and again. In our example algorithm calculated F₂ 7 times, F₃ 5 times and F₄ 3 times.

Can We Do Better ?

The answer is yes. We can do better by using Recursions with memoization which is the property of Dynamic Programming. It means we can store the value in memory when we computed it and then we can use it as many times as we want by just fetching it from memory.

Let's have a look

Let n be a number and memo be an array of size n+1 memo[n+1]
Fib(n,memo)
    if n is less than or equals to 1
        return 1
    else if memo[n] is already computed
        return memo[n]
    memo[n] = Fib(n-1,memo) + Fib(n-2,memo)

// C++ Code
// We will initialize the memo array with all its values by -1 which means that the value is not calculated yet
int Fib(int n,int memo[]){
    if(n <= 1){
        return 1;
    }
    else if(memo[n] > -1){
        return memo[n];
    } 
    memo[n] = Fib(n-1,memo) + Fib(n-2,memo);
    return memo[n];
}

Let's run the above C++ code with n = 40

It took only 0.002 seconds. This is how we can improve our algorithms using Dynamic Programming. Let's see the recurrence tree of F₇=13 with Memoization

NOTE: You can't apply memoization with distinct problems, it is helpfull only when the sub problems are same and occuring again and again.

Citations

Fibonacci number - Wikipedia