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:

Note: Join free Sanfoundry classes at Telegram or Youtube

 
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.

If you find any mistake above, kindly email to [email protected]

« Prev - Coin Change Problem using Dynamic Programming

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

Related Posts:

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

Recommended Articles: