Dynamic Programming 01

Given a number N, find the first N Fibonacci numbers. The first two number of the series are 1 and 1.

Problem link :- click here

Code

import java.util.Scanner;

//	PRINT FIRST N FIBONACCI NUMBERS

public class DynamicProgramming_01
{
	

        // Recursion and memoization
	static long fibonacci(int n, long arr[])
	{
		if(arr[n] != 0)
			return arr[n];
		
		if(n==1)
		{
			arr[1] = 1;
			return 1;
		}
		if(n==2)
		{
			arr[2] = 1;
			return 1;
		}
		else
		{
			long ans = fibonacci(n-1, arr) + fibonacci(n-2, arr);
			arr[n] = ans;
			return ans;
		}
	}

        // Dynamic programming
	static long[] fibonacci1(int n)
	{
		long arr[] = new long[n+1];
		
		arr[1] = 1;
		arr[2] = 1;
		
		for(int i=3; i<=n; i++)
			arr[i] = arr[i-1] + arr[i-2];
		
		return arr;
	}
	
	public static void main(String[] args)
	{
		Scanner s = new Scanner(System.in);
		
		int n = s.nextInt();
//		long[] ans = fibonacci1(n);
//		
//		for(long a: ans)
//			System.out.println(a);
		
		long[] arr = new long[n+1];
		
		long ans2 = fibonacci(n, arr);
		for(long a: arr)
			System.out.println(a);
		
		s.close();
	}

}