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

Note: Join free Sanfoundry classes at Telegram or Youtube

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:

Take Data Structure I Practice Tests - Chapterwise!
Start the Test Now: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

 
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

Next Steps:

Get Free Certificate of Merit in Data Structure I
Participate in Data Structure I Certification Contest
Become a Top Ranker in Data Structure I
Take Data Structure I Tests
Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Related Posts:

Practice Programming MCQs
Apply for Information Technology Internship
Practice Design & Analysis of Algorithms MCQ
Apply for Data Structure Internship
Apply for Computer Science Internship

Recommended Articles: