This is a C++ Program that Solves Fibonacci Numbers Problem using Dynamic Programming technique.
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]
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.
Case-1:
n=3 Expected result=2
Case-2:
n=4 Expected result=3
Case-3:
n=5 Expected result=5
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;
}
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;
}
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.
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.
- 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
- Practice Programming MCQs
- Apply for Information Technology Internship
- Practice Design & Analysis of Algorithms MCQ
- Apply for Data Structure Internship
- Apply for Computer Science Internship