// Arup Guha
// 3/29/2018
// Example of Recursion -> Memoization -> Dynamic Programming
// Fibonacci Problem

import java.util.*;

public class fib {

	final public static int N = 44;
	public static int[] fibarray;

	public static void main(String[] args) {

		/*** 1. make storage for all possible recursive calls fibarray[i] will store F(i) ***/
		fibarray = new int[N+1];

		/*** 2. Fill this storage with -1 or another sentinel to indicate we don't know these answers yet. ***/
		Arrays.fill(fibarray, -1);

		// Call both the memoized and DP versions.
		long start = System.currentTimeMillis();
		int res = fib(N);
		int res2 = fibdyn(N);
		long end = System.currentTimeMillis();
		
		// Output results and time for both.
		System.out.println("res is "+res+" and "+res2+" took "+(end-start)+" ms.");
	}

	public static int fib(int n) {
		
		// Our usual base case.
		if (n < 2) return n;

		/*** 3. In base case, check if we've done this before, if so, return the answer immediately. ***/
		if (fibarray[n] != -1) return fibarray[n];

		/*** 4. Store answer in memory before returning. ***/
		return fibarray[n] = fib(n-1) + fib(n-2);
	}

	// Traditional DP solution to the Fibonacci problem.
	public static int fibdyn(int n) {

		// Seed our storage with initial values needed to calculate f[2].
		int[] f = new int[n+1];
		f[0] = 0;
		f[1] = 1;

		// Instead of making recursive calls, just look up the array values.
		for (int i=2; i<=n; i++)
			f[i] = f[i-1] + f[i-2];

		return f[n];
	}
}