Finding Nth Fibonacci Number using Dynamic Programming ( Top Down DP )

 Nth Fibonacci Numbers using Dynamic Programming - Top Down DP 

One of the primary problems to understand Dynamic Programming ( DP ) is finding the nth Fibonacci number. Here, we will solve the problem using the top-down approach.

Problem statement :

You are given a number N. You need to find Nth Fibonacci number. The Fibonacci series is a sequence where the next term is the sum of the previous two terms

Example 1:

Input:

N = 5

Output: 5

Example 2:

Input:

N = 7

Output: 13

Explanation: Some of the numbers of the

Fibonacci numbers are 0,1, 1, 2, 3, 5, 8,13..... .

Your Task:

Your task is to write a program to find the Nth fibonacci number using Dynamic Programming ( DP )

Top Down DP.

Expected Time Complexity: O(N).

Expected Auxiliary Space: O(N).

Note: This space is used by dp array.

Recommended: Please try your approach on your integrated development environment (IDE) first, before moving on to the solution.

Few words from CodingHumans : Don't Just copy paste the solution, try to analyze the problem and solve it without looking by taking the the solution as a hint or a reference . Your understanding of the solution matters.

HAPPY CODING 😁

Solution

( Java )

import java.util.*;
public class nFibonacci {
	static long fib(long dp[],int n) //memorization Dynamic Programming
	{
		Arrays.fill(arr, -1);
		if(arr[n]==-1)
		{
			long res;
			if(n==0||n==1)
				res=n;
			else
				res=fib(dp,n-1)+fib(dp,n-2);
			arr[n]=res;
		}
		return arr[n];
	}
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		long dp[]=new int[n+1];
		System.out.println(fib(dp,n)); 
	}
}

Output

N = 5

Output: 5