How to implement an algorithm for computing Fibonacci numbers in C++ using DP

In this C++ tutorial, I will show you how to find Fibonacci number in C++. Learn how to implement an algorithm using dynamic programming (DP) to find a number, by just entering the position from the user, in the Fibonacci Sequence.

What is the Fibonacci Sequence?

In mathematics Fibonacci Sequence is a sequence in which each number is the sum of preceding two numbers. The first two elements of the Fibonacci sequence are 0 and 1.

         In fibonnaci sequence any number at position n is defined as :-

    f(x) = f(x-1) + f(x-2)   where f(1)=0, f(2)=1

What is Dynamic Programming?

Dynamic programming is an algorithm which optimizes the recursive problem. In problems where there is recursion and we call the same sub-problem, again and again, it increases the time complexity in computing for the same value again and again. In Dynamic programming value of sub-problem is stored and it does not need to be computed again and again which reduces the time complexity.

Problem Description

We are provided with a number ‘n’ we have to print the value of the element at that position in Fibonacci sequence using dynamic programming.

An algorithm to find the nth term of fibonnaci sequence in C++

1. Declare an array dp[n+1] which stores the values for each position element from 3 to n once of fibonnaci sequence.
2. Base case of dp are dp[1]=0 as first element of fibonnaci sequence is 0 and d[1]=1 as the second element of fibonnaci sequence is 1.
3. Store the value of element at each index i in array as dp[i]=dp[i-1]+dp[i-2] upto n.
4. print the value of dp[n] which is the value of element at position ‘n’ in fibonnaci sequence.

Find the nth term of a Fibonacci sequence in C++

 #include<bits/stdc++.h>

      using namespace std;
 
  int main()
 {
     long long n;
      
           cin>>n;
       
       int dp[n+1];
       
      
       dp[1]=0; // Base Case
       
       dp[2]=1; // Base Case
       
       for(long i=3;i<=n;i++)
            dp[i]=dp[i-1]+dp[i-2];
            
            cout<<dp[n]<<endl;
 }

Input

10

Output

34

Read more,

• Frequency of each character in a string using map in c++
• Mathematical functions in CPP