Fibonacci Series using Dynamic Programming

FibonacciWithDynamicProgramming.java

import java.util.Arrays;

public class FibonacciWithDynamicProgramming {
	
	public static void main(String[] args) {
		int n = 30;
		long starTime = System.nanoTime();
		System.out.println("Fibonacci without dynamic: " + fibonacci(n));
		long endTime = System.nanoTime();
		System.out.println("Time taken: " + (endTime - starTime));
		
		starTime = System.nanoTime();
		System.out.println("Fibonacci with dynamic: " + fibonacciDynamic(n));
		endTime = System.nanoTime();
		System.out.println("Time taken: " + (endTime - starTime));
	}
	
	private static int fibonacciDynamic(int n) {
		int[] arr = new int[n + 1];
		Arrays.fill(arr, -1);
		
		return getFibonacci(arr, n);
	}
	
	private static int getFibonacci(int[] arr, int n) {
		if (n <= 1) {
			return n;
		}
		
		if (arr[n] == -1) {
			arr[n] = getFibonacci(arr, n - 1) + getFibonacci(arr, n - 2);
			return arr[n];
		}
		
		return arr[n];
	}
	
	private static int fibonacci(int n) {
		if (n <= 1) {
			return n;
		} else {
			return fibonacci(n - 1) + fibonacci(n - 2);
		}
	}
}

/*
	Output:
		Fibonacci without dynamic: 832040
		Time taken: 18896963
		Fibonacci with dynamic: 832040
		Time taken: 147844            
 */