Home » Algorithms

Find the Nth Fibonacci number | C++

Here, we are going to learn how to find the Nth Fibonacci number using Dynamic programming in C++.
Submitted by Ritik Aggarwal, on November 07, 2018

Problem: Compute the N^th Fibonacci number

You are given a number N. You have to find the N^th Fibonacci number. 0^th Fibonacci number is 0 and first Fibonacci number is 1.

Sample inputs:

    N = 0, answer is 0
    N = 1, answer is 1
    N = 5, answer is 5

Basic Approach: Recursive approach

int fibonacci(int N){
    if(N == 0 || N == 1){
        return N;
    }
    int ans = fibonacci(N-1) + fibonacci(N - 2);
    return ans;
}

Now provided above is the basic recursive approach which takes O(2^N) time to compute as every call needs to call two other calls but if we already have the answers of two other calls in an array then we can directly use them.

Top Down Approach:

int fibonacciTopDown(int N, int strg[]){
    if(N == 1 || N == 0){
        return N;
    }
    if(strg[N] != 0){
        return strg[N];
    }
    int ans = fibonacciTopDown(N-1, strg) + fibonacciTopDown(N - 2, strg);
    strg[N] = ans;
    return ans;
}

Now the top down approach also uses recursion but before returning the answer to the solution we store the answer in strg array so that if we needed the answer again then we could simply use that answer directly from our array. The time complexity of the program is O(N).

Bottom Up Approach:

int fibonacciBottomUp(int N){
    int strg[N + 1] = {0};
    strg[0] = 0;
    strg[1] = 1;
    for(int i = 2;i<N+1;i++){
        strg[i] = strg[i-1] + strg[i-2];
    }
    return strg[N];
}

This is the Bottom Up approach with time complexity as O(N). Now we have an iterative method to the recursive problem.

As seen above from the dp approaches we can very easily see that storage matrix or dp matrix has some meaning. For example, In the Fibonacci case, the N^th index of strg matrix stores the N^th fibonaaci number that's why we can very easily write this line strg[i] = strg[i-1] + strg[i-2].

As stated above start solving dp problems with recursion first and then proceed to dp. Try assigning some meaning to the storage matrix or dp matrix and formulate the correct equation.

Code to find the Nth Fibonacci number using all given approaches

#include <iostream>
using namespace std;

int fibonacci(int N){
	if(N == 0 || N == 1){
		return N;
	}
	int ans = fibonacci(N-1) + fibonacci(N - 2);
	return ans;
}

int fibonacciTopDown(int N, int strg[]){
	if(N == 1 || N == 0){
		return N;
	}
	if(strg[N] != 0){
		return strg[N];
	}
	int ans = fibonacciTopDown(N-1, strg) + fibonacciTopDown(N - 2, strg);
	strg[N] = ans;
	return ans;
}

int fibonacciBottomUp(int N){
	int strg[N + 1] = {0};
	strg[0] = 0;
	strg[1] = 1;
	for(int i = 2;i<N+1;i++){
		strg[i] = strg[i-1] + strg[i-2];
	}
	return strg[N];
}

int main() {
	int N;
	cin >> N;

	int strg[N + 1] = {0};
	cout << "The answer using recursive solution is " << fibonacci(N) << endl;
	cout << "The answer using Bottom up aproach is " << fibonacciBottomUp(N) << endl;
	cout << "The answer using Top down approach is " << fibonacciTopDown(N,strg) << endl;

	return 0;
}

Output

8
The answer using recursive solution is 21
The answer using Bottom up aproach is 21
The answer using Top down approach is 21