10.1. Fibonacci Sequence

public interface Fibonacci {
    int get(int k);
}

public class FibonacciRecursive implements Fibonacci {
    @Override
    public int get(int k) {
        return switch (k) {
            case 0 -> 0;
            case 1 -> 1;
            default -> get(k - 1) + get(k - 2);
        };
    }
}

public class FibonacciDynamic implements Fibonacci {
    @Override
    public int get(int k) {
        return getAux(k, createTable(k));
    }
    
    private int[] createTable(int k) {
        int[] table = new int[k + 1];
        table[0] = 0;
        table[1] = 1;
        Arrays.fill(table, 2, k + 1, -1);
        return table;
    }

    private int getAux(int k, int[] table) {
        if (table[k] >= 0) return table[k];
        return table[k] = getAux(k - 1, table) + getAux(k - 2, table);
    }
}

public class FibonacciIterative implements Fibonacci {
    @Override
    public int get(int k) {
        if (k < 2) return k;
        int f0 = 0, f1 = 1, f2;

        for (int i = 2; i < k; i++) {
            f2 = f0 + f1;
            f0 = f1;
            f1 = f2;
        }

        return f0 + f1;
    }
}