Fibonacci Series Java Program - The Coding Shala

Home >> Programming Questions >> Fibonacci Series

Fibonacci Series Java Program

In this post, you will learn how to write a Java program to print the Fibonacci Series or Fibonacci Sequence.

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is, 
F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), for N > 1.
Given N, calculate F(N).

The Fibonacci series starts with 0 and the second number is 1. In the Fibonacci series, the third number is the sum of the first and second numbers. We can print the nth number in the Fibonacci series by adding the previous two numbers of the Fibonacci series.
Example 1:
Input: 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.


Example 2:

Input: 3

Output: 2

Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Fibonacci Number Java Program


Approach 1:

Using Dynamic Programming we can store all the numbers of the Fibonacci series.
Java Program: 

class Solution {
    public int fib(int N) {
        if(N<2) return N;
        int[] dp = new int[N+1];
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2; i<=N; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[N];
    }
}

Approach 2:
Using Recursion.
Java Program: 

class Solution {
    public int fib(int N) {
        if(N<2) return N;
        return fib(N-1)+fib(N-2);
    }
}

Approach 3:
Using Recursion and Memoization. We can use HashMap to store intermediate results so no need to calculate duplicate results again.
Java Program: 

class Solution {
    HashMap<Integer, Integer> cache = new HashMap<Integer, Integer>();
    public int fib(int N) {
        if(cache.containsKey(N)){
            return cache.get(N);
        }
        int result;
        if(N<2){
            result = N;
        }else{
            result = fib(N-1)+fib(N-2);
        }
        cache.put(N,result);
        return result;
    }
}


Other Posts You May Like
Please leave a comment below if you like this post or found some error, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Richest Customer Wealth LeetCode Solution - The Coding Shala

New Year Chaos Solution - The Coding Shala

Add two numbers in Scala - The Coding Shala