Program to find nth fibonacci number by dynamic programming
Program to find nth fibonacci number by dynamic programming
Given a number , write a Program to find nth fibonacci number by dynamic programming .
Sample input:-
9
Sample output:-
9th fibonacci number is 34
Program to find nth fibonacci number by dynamic programming:-
The objective of the code is to the nth fibonacci number . Here first we write a recursive code for the finding the fibonacci number.
Code (Using recursion):-
#include<bits/stdc++.h> using namespace std; // Recursive function for finding the fibonacci number int findFibbo(int n ) { if(n<=1) return 1; return findFibbo(n-1)+findFibbo(n-2); } int main() { int n; cout<<"Enter a number"<<endl; cin>>n; cout<<n<<"th findFibbo number is "<<findFibbo(n); return 0; }
Output:-
Enter a number 9 9th fibonacci number is 34
Time Complexity:- Ο(n)
Space complexity:- Ο(n) + Ο(n) { Extra O(n) for recursion stack space}
But when we use this method then there are many overlapping problems occurs that means we have to calculate the value of many problems again and again .For better understanding see the example:-
Here as we can see we have to calculate f(2) more than once so that we can solve this problem using dynamic programming.
Method 2 (using DP) :-
Code(C++):-
#include<bits/stdc++.h> using namespace std; // Recursive function for finding the fibonacci number int findFibbo(int n ,vector<int>&dp) { if(n<=1) return n; if(dp[n]!=-1) return dp[n]; return dp[n]=findFibbo(n-1,dp)+findFibbo(n-2,dp); } int main() { int n; cout<<"Enter a number"<<endl; cin>>n; vector<int> dp(n+1,-1); cout<<n<<"th fibonacci number is "<<findFibbo(n,dp); return 0; }
Code (Java):-
import java.util.*; public class Main { public static int Fib(int n, int dp[]) { if(n<=1) { return n; } if(dp[n]!= -1) { return dp[n]; } return dp[n] = Fib(n-1,dp)+Fib(n-2,dp); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int dp[] = new int[n+1]; Arrays.fill(dp,-1); System.out.print(n+"th fibonacci number is "+Fib(n,dp)); } }
Output:-
Enter a number 9 9th fibonacci number is 34
Time Complexity:- Ο(n)
Space complexity:- Ο(n) + Ο(n) { Extra O(n) for recursion stack space}
Method 3 (using DP {Tabulation}):-
#include<bits/stdc++.h> using namespace std; int main() { int n; cout<<"Enter a number"<<endl; cin>>n; vector<int> dp(n+1,-1); dp[0]=0; dp[1]=1; for(int i=2;i<=n;i++) { dp[i]=dp[i-1]+dp[i-2]; } cout<<n<<"th fibonacci number is "<<dp[n]; return 0; }
Output:-
Enter a number 9 9th fibonacci number is 34
Time Complexity:- Ο(n)
Space complexity:- Ο(n)
We can optimize the space by instead of using array we can use two variable for storing previous two values.
Method 4 (space optimized):-
// space optimize code for fibonacci #include<bits/stdc++.h> using namespace std; int main() { int n; cout<<"Enter a number"<<endl; cin>>n; int prev2,pre,curr; prev2=0; pre=1; for(int i=2;i<=n;i++) { curr=pre+prev2; prev2=pre; pre=curr; } cout<<n<<"th fibonacci number is "<<curr<<endl; return 0; }
Output:-
Enter a number 9 9th fibonacci number is 34
Time Complexity:- Ο(n)
Space complexity:- Ο(1)
Recommended Post:-
- Primary test
- Sum or difference
- point and line
Wipro :-
- Update the booking ID | Wipro previous year question paper solution
- Pages in PDF
- Find the location id
- Find the odd digits
- Find the Product ID
Infytq :-
Key Points;-
Hackerrank:-
- Python : missing characters : hackerrank solution
- Python : string transformation | Hackerrank solution
- Active Traders certification test problem | Hackerrank Solution
- Usernames changes certification test problem | Hackerrank Solution
- string Representation of objects certification test hackerrank solution
- Average Function | hackerrank certification problem solution
C-tutorial:-
- Micros in C
- Pointer in c
- Function declaration
- Types of user define function
- return type of function
- 2D array
See more:-
- c program to convert specified days into years weeks and days
- Print Reverse Hollow Pyramid
- Update the booking ID | Wipro previous year question paper
- Pages in PDF | Wipro previous year question paper
- Sparse Matrix in data structure
- Find the location ID | Wipro previous year Coding question
- find the odd digits | Wipro Coding question
- Find the product id | Wipro Coding question
- Difference between static and dynamic memory allocation
- What is asymptotic Notation