# 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++

- Declare an array dp[n+1] which stores the values for each position element from 3 to n once of fibonnaci sequence.
- 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.
- Store the value of element at each index i in array as dp[i]=dp[i-1]+dp[i-2] upto n.
- 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,

## Leave a Reply