Fibonacci Series using Dynamic Programming

This is a C++ Program that Solves Fibonacci Numbers Problem using Dynamic Programming technique.

Problem Description

Find nth fibonacci number

The Fibonacci Sequence is the series of numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …
The next number is found by adding up the two numbers before it.

Let F[i] be the ith fibonacci number

F[0]=0
F[1]=1

F[i]=F[i-1]+F[i-2]

Problem Solution

This problem can be solved very easily by using recursion. But this is not an efficient solution. Using DP, we can solve this problem in O(n). We will proceed in a bottom up manner and keep caching all the values to avoid recomputation.

Expected Input and Output

Case-1:

 
n=3
Expected result=2

Case-2:

Free 30-Day Java Certification Bootcamp is Live. Join Now!

 
n=4
Expected result=3

Case-3:

 
n=5
Expected result=5

Program/Source Code for Recursive Solution

Here is source code of the C++ Program to Solve Fibonacci Numbers Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include<iostream>
```
```
using namespace std;
```
```
 
```
```
int fibonacci(int n)
```
```
{
```
```
    if(n<=1)
```
```
        return n;
```
```
 
```

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

```
}
```
```
 
```
```
int main()
```
```
{
```
```
    int n;
```
```
    cout<<"Enter the value of n"<<endl;
```
```
    cin>>n;
```
```
 
```

    cout<<"Required fibonacci number is ";

```
    cout<<fibonacci(n);
```
```
 
```
```
    cout<<endl;
```
```
    return 0;
```
```
}
```

Program/Source Code for DP solution

Here is source code of the C++ Program to Solve Fibonacci Numbers Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include<iostream>
```
```
using namespace std;
```
```
 
```
```
int fibonacci(int n)
```
```
{
```
```
    int F[n+1];
```
```
 
```
```
    F[0]=0;
```
```
    F[1]=1;
```
```
 
```
```
    for(int i=2;i<=n;i++)
```
```
        F[i]=F[i-1]+F[i-2];
```
```
 
```
```
    return F[n];
```
```
}
```
```
 
```
```
int main()
```
```
{
```
```
    int n;
```
```
    cout<<"Enter the value of n"<<endl;
```
```
    cin>>n;
```
```
 
```

    cout<<"Required fibonacci number is ";

```
    cout<<fibonacci(n);
```
```
 
```
```
    cout<<endl;
```
```
    return 0;
```
```
}
```

Program Explanation

In the main function, we ask the user to input the value of n. We pass this value to the function buildingProblem as parameter. This function will calculate the expected result and return it. The returned value will be displayed.

Runtime Test Cases

 
Case-1:
$ g++ fibonacci.cpp
$ ./a.out
Enter the value of n
6
Required fibonacci number is 8

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.

« Prev - Coin Change Problem using Dynamic Programming

» Next - Binary Trees with N Keys Problem – Dynamic Programming Solutions

Related Posts:

Recommended Articles: