Fibonacci Numbers

Question

Find the Nth number in fibonacci numbers

Algorithm

• fib(n) = fib(n - 1) + fib(n - 2)
• Use an array lookup to store ith fibonacci number to repetitive computation

Code

public class Fib {

    private int[] lookup;

    public int fibRecursive(int n) {
        lookup = new int[n + 1];
        Arrays.fill(lookup, -1);
        return helper(n);
    }

    private int helper(int n) {
        if (lookup[n] == -1) {
            if (n <= 1) {
                lookup[n] = n;
            } else {
                lookup[n] = helper(n - 1) + helper(n - 2);
            }
        }
        return lookup[n];
    }

    public int fibIterative(int n) {
        int[] fib = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            if (i <= 1) {
                fib[i] = i;
            } else {
                fib[i] = fib[i - 1] + fib[i - 2];
            }
        }
        return fib[n];
    }

    public static void main(String[] args) {
        Fib fib = new Fib();
        System.out.println(fib.fibIterative(9));
    }
}