Program to find nth fibonacci number by dynamic programming

Program to find nth fibonacci number by dynamic programming

Given a number , write a Program to find nth fibonacci number by dynamic programming .

Sample input:-

9

Sample output:-

9th fibonacci number is 34

Program to find nth fibonacci number by dynamic programming:-

The objective of the code is to the nth fibonacci number . Here first we write a recursive code for the finding the fibonacci number.

Code (Using recursion):-

#include<bits/stdc++.h>
using namespace std;

// Recursive function for finding the fibonacci number
int findFibbo(int n )
{
    if(n<=1)
        return 1;
    return findFibbo(n-1)+findFibbo(n-2);
}
int main()
{
    
    int n;
    cout<<"Enter a number"<<endl;
    cin>>n;
    cout<<n<<"th findFibbo number is "<<findFibbo(n);
    return 0;
}

Output:-

Enter a number
9
9th fibonacci number is 34

 

Time Complexity:-  Ο(n)

Space complexity:-  Ο(n) + Ο(n)  { Extra O(n) for recursion stack space}

But when we use this method then there are many overlapping problems occurs that means we have to calculate the value of many problems again and again .For better understanding see the example:-

 

Here as we can see we have to calculate f(2) more than once so that we can solve this problem using dynamic programming.

Method 2 (using DP) :- 

Code(C++):-

#include<bits/stdc++.h>
using namespace std;

// Recursive function for finding the fibonacci number
int findFibbo(int n ,vector<int>&dp)
{
    if(n<=1)
        return n;
    if(dp[n]!=-1)
     return dp[n];
    return dp[n]=findFibbo(n-1,dp)+findFibbo(n-2,dp);
}
int main()
{
    
    int n;
    cout<<"Enter a number"<<endl;
    cin>>n;
    vector<int> dp(n+1,-1);
    cout<<n<<"th fibonacci number is "<<findFibbo(n,dp);
    return 0;
}

Code (Java):-

import java.util.*;
public class Main
{
    public static int Fib(int n, int dp[])
    {
        if(n<=1)
        {
            return n;
        }
        if(dp[n]!= -1)
        {
            return dp[n];
        }
        return dp[n] = Fib(n-1,dp)+Fib(n-2,dp);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int dp[] = new int[n+1];
        Arrays.fill(dp,-1);
        System.out.print(n+"th fibonacci number is "+Fib(n,dp));
    }
}

 

Output:-

Enter a number
9
9th fibonacci number is 34

Time Complexity:-  Ο(n)

Space complexity:-  Ο(n) + Ο(n)   { Extra O(n) for recursion stack space}

 

Method 3 (using DP {Tabulation}):-

#include<bits/stdc++.h>
using namespace std;

int main()
{
    
    int n;
    cout<<"Enter a number"<<endl;
    cin>>n;
    vector<int> dp(n+1,-1);
    dp[0]=0;
    dp[1]=1;
    for(int i=2;i<=n;i++)
    {
        dp[i]=dp[i-1]+dp[i-2];
    }
    
    cout<<n<<"th fibonacci number is "<<dp[n];
    return 0;
}

Output:-

Enter a number
9
9th fibonacci number is 34

Time Complexity:-  Ο(n)

Space complexity:-  Ο(n)   

We can optimize the space by instead of using array we can use two variable for storing previous two values.

Method 4 (space optimized):-

// space optimize code for fibonacci

#include<bits/stdc++.h>
using namespace std;

int main()
{
    
    int n;
    cout<<"Enter a number"<<endl;
    cin>>n;
    int prev2,pre,curr;
    prev2=0;
    pre=1;
    for(int i=2;i<=n;i++)
    {
        curr=pre+prev2;
        prev2=pre;
        pre=curr;
    }
    cout<<n<<"th fibonacci number is "<<curr<<endl;
    return 0;
}

Output:-

Enter a number
9
9th fibonacci number is 34

Time Complexity:-  Ο(n)

Space complexity:-  Ο(1)

 

Recommended Post:-