# 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=0 as first element of fibonnaci sequence is 0 and d=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=0; // Base Case

dp=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`