Fibonacci numbers with help of DP

Well...the most and simple program which every programmer may have solved at least once....

Fibonacci numbers:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……..

In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation....

with base condition

f(0)=0 

f(1)=1

In general:

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

Basic Approach:

A simple method that is a direct recursive implementation mathematical recurrence relation given above

Here is simple CPP program....

#include<bits/stdc++.h>

using namespace std;

  

int fib(int n)

{

    if (n <= 1)

        return n;

    return fib(n-1) + fib(n-2);

}

  

int main ()

{

    int n = 9;

    cout << fib(n);

    return 0;

}

That was simple....isn't it.....

But what is wrong in the above approach....

lets see....

                            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)

Here we can see that the values are calculated again and again....

like fib(3) is calculated twice....

Time Complexity: T(n) = T(n-1) + T(n-2) which is exponential.

So can we do better....?

YES.....we can....

Remember...we discuss something about DP.....

Lets see the Efficient approach..

#include<bits/stdc++.h>

using namespace std; 

int fib(int n)

{

  int f[n+2];  

  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;

  cout<<fib(n);

  return 0;

}




What are we doing different in this approach and why it is better than

recursive approach...

In this approach we compute every term only once...and store it in the

array which we can use in the future for calculating the new value...