public class Fibonacci {

    /**
     * the array to memorize computed results
     */
    private static long[] memo;

    /**
     * count acesses on a precomputed fibnacci number
     */
    private static int[] savings;

    /**
     * initialize memo structure
     */
    private static void initMemo(int k) {
	if (k < 2) { k = 2; }
	memo = new long[k + 1];
	savings = new int[k + 1];

	memo[0] = 0;
	memo[1] = 1;
	for (int i = 2; i <= k; ++i) {
	    memo[i] = 0;
	}
    }

    /**
     * compute the k-th fibonacci number rekursively using memoization
     */
    public static long computeMemoization(final int k) {
	if (k > 1 && memo[k] == 0) {
	    // rekursively compute F_k
	    memo[k] = computeMemoization(k-1) + computeMemoization(k-2);
	    return memo[k];
	} else {
	    if (k > 1) {  // only for counting duplicate computations
		savings[k]++;
		computeMemoization(k-1);
		computeMemoization(k-2);
	    }
	    return memo[k];  // return memoized value of F_k
	}
    }

    /**
     * compute the k-th fibonacci number iteratively 
     */
    public static long computeDynProg(final int k) {
	// compute fibonacci number iteratively
	for (int i = 2; i <= k; ++i) {
	    memo[i] = memo[i-2] + memo[i-1];
	}

	return memo[k];
    }

    public static void main(String[] args) {
	if (args.length != 1) {
	    System.out.println("usage: java Fibonacci k");
	    return;
	}

	final int k = Integer.parseInt(args[0]);

	initMemo(k);
	System.out.println("Fibonacci Memoization: " + computeMemoization(k));
	int total_savings = 0;
	for(int i = 0; i <= k; ++i) {
	    total_savings += savings[i];
	}
	System.out.println("saved computations: " + total_savings);
	initMemo(k);
	System.out.println("Fibonacci DynProg: " + computeDynProg(k));
    }
}