Java Program to find Nth term of Fibonacci series

This problem can be solved very easily by using recursion. But this is not an efficient solution. Using Dynamic Programming, we can solve this problem in O(n). We will proceed in a bottom up manner and keep caching all the values to avoid re-computation. For this, we use memoization by combining recursion and storing the values in array.

Memoization is a technique for improving the performance of recursive algorithms.

---

Implementation Using Java:

import java.util.Scanner;
public class Fibonacci {
	private static int fib(int n, int[] dp) {
		if(n==0||n==1)
		{
			return n;
		}
		int ans1, ans2;
		if(dp[n-1]==-1)
		{
			ans1=fib(n-1,dp);
			dp[n-1]=ans1;
		}
		else
		{
			ans1=dp[n-1];
		}
		if(dp[n-2]==-1)
		{
			ans2=fib(n-2,dp);
			dp[n-2]=ans2;
		}
		else
		{
			ans2=dp[n-2];
		}
		int myAns=ans1+ans2;
		return myAns;
	}
		public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		System.out.println("Enter the term");
		int n=sc.nextInt();
		int[] dp=new int[n+1];
		
		for(int i=0;i<dp.length;i++)
		{
			dp[i]=-1;
		}
		int ans= fib(n,dp);
		System.out.println("The"+" "+n+" "+"term of Fibonacci         is"+ans);
	}
}

---

Happy Coding!

Follow us on Instagram @programmersdoor

Join us on Telegram @programmersdoor

Please write comments if you find any bug in above code/algorithm, or find other ways to solve the same problem.

Follow Programmers Door for more.

#blog #interview #placement #learn #computer #science