Nth number in a Fibonacci series using Dynamic Programming in Java

In this Java tutorial, we are going to find nth number in a Fibonacci series using dynamic programming bottom-up approach.

Why Dynamic Programming?

The given problem can also be solved with other approaches like recursive function calling but they take exponential time. Dynamic programming prevents solving the same sub-problem again which reduces time-complexity to linear.

What is a bottom-up approach in Dynamic Programming?

In the bottom-up approach in dynamic programming, we start with the state which we already know and store its value in array. Then we iteratively proceed through the further problem by increasing the value of n.

Algorithm to find out the Nth number in a Fibonacci series in java

  1. Input a value n, value of whose position we have to find in Fibonacci series.
  2. Then take an array dp[] and build up a table in bottom-up order using known value for n=0 and n=1.
  3. Build up the table by increasing value of n iteratively using dp[i] = dp[i-1]+dp[i-2].
  4. Return dp[n] as our answer.

Learn Java Program To Make Fibonacci Series With Explanation

Code Snippet to build up the table in bottom-up manner

  
for(int i=2;i<=n;i++)
 
 dp[i]=dp[i-1]+dp[i-2];
 

Java Code to print nth number in Fibonacci series

import java.util.Scanner;

  class Codespeedy
{
     
        public static int result(int 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];
    }
    
    public static void main(String[] args)
  {
      Scanner scan = new Scanner(System.in);
      
    System.out.println("Enter the number:");
     
           int n=scan.nextInt();
      
      System.out.println(result(n));
  }
}

INPUT



3

OUTPUT

2

So, Fibonacci series upto 3 is 0, 1, 2. The element at the 3rd position is 2.

 

Leave a Reply

Your email address will not be published. Required fields are marked *