/**
 * F(n) = F(n - 1) + F(n - 2), F(0) = 0, F(1) = 1
 */
public class Fib{
    private static long[] M = new long[1000];
    private static long calls = 0;
    private static long callsDP = 0;
    /**
     * Recursive implementation for Fibonacci sequence
     */
    public static long fib(int n){
        ++calls;
        if( n <= 1){
            return n;
        }
        return fib(n-1) + fib(n-2);
    }

    /**
     * Dynamic programming implementation for Fibonacci sequence
     */
    public static long fibDP(int n){
        ++callsDP;
        if( n <= 1){
            return n;
        }
        if( M[n] == 0 ){
            M[n] = fibDP(n-1) + fibDP(n-2);
        }
        return M[n];
    }
    /**
     * Dynamic programming iterative implementation for Fibonacci sequence
     */
    public static long fibDPIter(int n){
        for( int i = 2; i <= n; ++i){
            M[i] = M[i-1] + M[i-2];
        }
        return M[n];
    }


    public static void main( String[] args){
        M[0] = 0;
        M[1] = 1;
        for(int i = 16; i <= 94; i+=2){
            //System.out.println("fib("+i+") = " + fib(i) + " ("+calls + " calls)");
            System.out.println("fibDP("+i+") = " + fibDP(i) + " ("+callsDP + " calls)");
            System.out.println("fibDPIter("+i+") = " + fibDPIter(i));
        }
    }
}